← Home
For problem statement at 1000-1999/1700-1799/1720-1729/1720/problemD2.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1720-1729/1720/verifierD2.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

type Node struct {
	child  [2]int32
	max_dp [2]int32
}

func readInt(reader *bufio.Reader) int {
	var res int
	var sign int = 1
	for {
		c, err := reader.ReadByte()
		if err != nil {
			return res * sign
		}
		if c == '-' {
			sign = -1
		} else if c >= '0' && c <= '9' {
			res = res*10 + int(c-'0')
			break
		}
	}
	for {
		c, err := reader.ReadByte()
		if err != nil {
			return res * sign
		}
		if c >= '0' && c <= '9' {
			res = res*10 + int(c-'0')
		} else {
			break
		}
	}
	return res * sign
}

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 65536)
	writer := bufio.NewWriterSize(os.Stdout, 65536)
	defer writer.Flush()

	t := readInt(reader)
	if t == 0 {
		return
	}

	tr := make([]Node, 1, 10000000)

	for tc := 0; tc < t; tc++ {
		n := readInt(reader)

		tr = tr[:1]
		tr[0] = Node{}

		maxLen := int32(0)
		for i := 0; i < n; i++ {
			a_i := readInt(reader)
			X_i := a_i ^ i

			ans := int32(0)
			curr := int32(0)
			for d := 29; d >= 0; d-- {
				bit_X := (X_i >> d) & 1
				bit_a := (a_i >> d) & 1

				diff_child := tr[curr].child[1^bit_X]
				if diff_child != 0 {
					req_j := 1 ^ bit_a
					if tr[diff_child].max_dp[req_j] > ans {
						ans = tr[diff_child].max_dp[req_j]
					}
				}

				curr = tr[curr].child[bit_X]
				if curr == 0 {
					break
				}
			}

			dp := ans + 1
			if dp > maxLen {
				maxLen = dp
			}

			curr = 0
			for d := 29; d >= 0; d-- {
				bit_X := (X_i >> d) & 1
				bit_i := (i >> d) & 1

				if tr[curr].child[bit_X] == 0 {
					tr = append(tr, Node{})
					tr[curr].child[bit_X] = int32(len(tr) - 1)
				}
				curr = tr[curr].child[bit_X]
				if dp > tr[curr].max_dp[bit_i] {
					tr[curr].max_dp[bit_i] = dp
				}
			}
		}
		fmt.Fprintln(writer, maxLen)
	}
}