For problem statement at 1000-1999/1700-1799/1770-1779/1777/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1770-1779/1777/verifierF.go ends with All tests passed can you fix the verifier? package main
import (
"bytes"
"io"
"os"
"strconv"
)
const (
MaxN = 200000
MaxNodes = 6200200
)
var ch0 = make([]int32, MaxNodes)
var ch1 = make([]int32, MaxNodes)
var cnt = make([]int32, MaxNodes)
var nodes int32
type FastScanner struct {
data []byte
idx int
n int
}
func NewFastScanner() *FastScanner {
data, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: data, n: len(data)}
}
func (fs *FastScanner) NextInt() int {
for fs.idx < fs.n {
c := fs.data[fs.idx]
if (c >= '0' && c <= '9') || c == '-' {
break
}
fs.idx++
}
sign := 1
if fs.data[fs.idx] == '-' {
sign = -1
fs.idx++
}
val := 0
for fs.idx < fs.n {
c := fs.data[fs.idx]
if c < '0' || c > '9' {
break
}
val = val*10 + int(c-'0')
fs.idx++
}
return sign * val
}
func clone(from int32) int32 {
idx := nodes
nodes++
ch0[idx] = ch0[from]
ch1[idx] = ch1[from]
cnt[idx] = cnt[from]
return idx
}
func insert(prev int32, val int) int32 {
newRoot := clone(prev)
cnt[newRoot]++
curNew := newRoot
curPrev := prev
for b := 29; b >= 0; b-- {
if (val>>b)&1 == 0 {
nextPrev := ch0[curPrev]
nextNew := clone(nextPrev)
ch0[curNew] = nextNew
curNew = nextNew
curPrev = nextPrev
} else {
nextPrev := ch1[curPrev]
nextNew := clone(nextPrev)
ch1[curNew] = nextNew
curNew = nextNew
curPrev = nextPrev
}
cnt[curNew]++
}
return newRoot
}
func query(rootR, rootL int32, val int) int {
res := 0
curR, curL := rootR, rootL
for b := 29; b >= 0; b-- {
if (val>>b)&1 == 0 {
nr, nl := ch1[curR], ch1[curL]
if cnt[nr] != cnt[nl] {
res |= 1 << b
curR, curL = nr, nl
} else {
curR, curL = ch0[curR], ch0[curL]
}
} else {
nr, nl := ch0[curR], ch0[curL]
if cnt[nr] != cnt[nl] {
res |= 1 << b
curR, curL = nr, nl
} else {
curR, curL = ch1[curR], ch1[curL]
}
}
}
return res
}
func main() {
fs := NewFastScanner()
t := fs.NextInt()
var out bytes.Buffer
for ; t > 0; t-- {
n := fs.NextInt()
a := make([]int, n+1)
pref := make([]int, n+1)
for i := 1; i <= n; i++ {
a[i] = fs.NextInt()
pref[i] = pref[i-1] ^ a[i]
}
prevGE := make([]int, n+1)
nextG := make([]int, n+1)
stack := make([]int, 0, n)
for i := 1; i <= n; i++ {
for len(stack) > 0 && a[stack[len(stack)-1]] < a[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
prevGE[i] = 0
} else {
prevGE[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
stack = stack[:0]
for i := n; i >= 1; i-- {
for len(stack) > 0 && a[stack[len(stack)-1]] <= a[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
nextG[i] = n + 1
} else {
nextG[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
nodes = 1
roots := make([]int32, n+2)
for i := 0; i <= n; i++ {
roots[i+1] = insert(roots[i], pref[i])
}
ans := 0
for i := 1; i <= n; i++ {
leftL := prevGE[i]
leftR := i - 1
rightL := i
rightR := nextG[i] - 1
if i-prevGE[i] <= nextG[i]-i {
rRoot := roots[rightR+1]
lRoot := roots[rightL]
base := a[i]
for k := leftL; k <= leftR; k++ {
v := query(rRoot, lRoot, base^pref[k])
if v > ans {
ans = v
}
}
} else {
rRoot := roots[leftR+1]
lRoot := roots[leftL]
base := a[i]
for k := rightL; k <= rightR; k++ {
v := query(rRoot, lRoot, base^pref[k])
if v > ans {
ans = v
}
}
}
}
out.WriteString(strconv.Itoa(ans))
out.WriteByte('\n')
}
_, _ = os.Stdout.Write(out.Bytes())
}