← Home
For problem statement at 0-999/500-599/500-509/504/problemD.txt this is a correct solution, but verifier at 0-999/500-599/500-509/504/verifierD.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"math/big"
	"math/bits"
	"os"
	"strconv"
)

const size = 35

type Bitset [size]uint64

func xor(a, b *Bitset) {
	for i := 0; i < size; i++ {
		a[i] ^= b[i]
	}
}

func highestBit(a *Bitset) int {
	for i := size - 1; i >= 0; i-- {
		if a[i] != 0 {
			return i*64 + bits.Len64(a[i]) - 1
		}
	}
	return -1
}

func parse(s string) *Bitset {
	n := new(big.Int)
	n.SetString(s, 10)
	bytes := n.Bytes()
	res := new(Bitset)
	for i := 0; i < len(bytes); i++ {
		b := bytes[len(bytes)-1-i]
		res[i/8] |= uint64(b) << (8 * (i % 8))
	}
	return res
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	m, _ := strconv.Atoi(scanner.Text())

	basis := make([]*Bitset, size*64)
	subset := make([]*Bitset, size*64)

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	for k := 0; k < m; k++ {
		if !scanner.Scan() {
			break
		}
		s := scanner.Text()
		v := parse(s)
		sub := new(Bitset)
		sub[k/64] |= 1 << (uint(k) % 64)

		for {
			hb := highestBit(v)
			if hb == -1 {
				break
			}
			if basis[hb] != nil {
				xor(v, basis[hb])
				xor(sub, subset[hb])
			} else {
				basis[hb] = v
				subset[hb] = sub
				break
			}
		}

		if highestBit(v) == -1 {
			var ans []int
			for i := 0; i < k; i++ {
				if (sub[i/64] & (1 << (uint(i) % 64))) != 0 {
					ans = append(ans, i)
				}
			}
			writer.WriteString(strconv.Itoa(len(ans)))
			for _, idx := range ans {
				writer.WriteByte(' ')
				writer.WriteString(strconv.Itoa(idx))
			}
			writer.WriteByte('\n')
		} else {
			writer.WriteString("0\n")
		}
	}
}