For problem statement at 1000-1999/1500-1599/1590-1599/1592/problemE.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1590-1599/1592/verifierE.go ends with test 6 mismatch: expected 4, got 6
Input:
33
972464319 587283587 89369679 979601222 619496396 737514589 574444257 234121166 842885789 685049292 73681021 558623584 424149763 186621696 601797763 651021215 346363002 911096849 309266085 501368116 539380949 877078440 26423865 941154155 317892009 918761425 841035871 636661496 321124397 319720390 509623386 932152941 917396784
Candidate output:
6
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"runtime/debug"
)
func init() {
debug.SetGCPercent(-1)
}
const MAX_NODES = 21000050
var child [MAX_NODES][2]int32
var count [MAX_NODES]int32
var roots [1000005]int32
var nodeCnt int32 = 0
func insert(prev int32, val int) int32 {
nodeCnt++
curr := nodeCnt
root := curr
for b := 19; b >= 0; b-- {
count[curr] = count[prev] + 1
bit := (val >> b) & 1
child[curr][0] = child[prev][0]
child[curr][1] = child[prev][1]
nodeCnt++
child[curr][bit] = nodeCnt
curr = nodeCnt
prev = child[prev][bit]
}
count[curr] = count[prev] + 1
return root
}
func exists(L_idx, R_idx, X_r, V int) bool {
if V == 0 {
return false
}
if L_idx > R_idx {
return false
}
u := roots[R_idx+1]
v := roots[L_idx]
for b := 19; b >= 0; b-- {
if count[u] == count[v] {
return false
}
bit_X := (X_r >> b) & 1
bit_V := (V >> b) & 1
if bit_V == 1 {
child_u := child[u][bit_X]
child_v := child[v][bit_X]
if count[child_u] > count[child_v] {
return true
}
u = child[u][1^bit_X]
v = child[v][1^bit_X]
} else {
u = child[u][bit_X]
v = child[v][bit_X]
}
}
return false
}
var scanner *bufio.Scanner
func nextInt() int {
scanner.Scan()
res := 0
b := scanner.Bytes()
for _, v := range b {
res = res*10 + int(v-'0')
}
return res
}
func main() {
scanner = bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
scanner.Buffer(make([]byte, 1024*1024), 1024*1024*10)
scanner.Scan()
b := scanner.Bytes()
if len(b) == 0 {
return
}
n := 0
for _, v := range b {
n = n*10 + int(v-'0')
}
a := make([]int, n+1)
X := make([]int, n+1)
roots[1] = insert(0, X[0])
for i := 1; i <= n; i++ {
a[i] = nextInt()
X[i] = X[i-1] ^ a[i]
roots[i+1] = insert(roots[i], X[i])
}
type Segment struct {
val int
L int
R int
}
segments := make([]Segment, 0, 25)
newSegments := make([]Segment, 0, 25)
ans := 0
for r := 1; r <= n; r++ {
newSegments = newSegments[:0]
for _, seg := range segments {
v := seg.val & a[r]
if len(newSegments) > 0 && newSegments[len(newSegments)-1].val == v {
newSegments[len(newSegments)-1].R = seg.R
} else {
newSegments = append(newSegments, Segment{val: v, L: seg.L, R: seg.R})
}
}
if len(newSegments) > 0 && newSegments[len(newSegments)-1].val == a[r] {
newSegments[len(newSegments)-1].R = r
} else {
newSegments = append(newSegments, Segment{val: a[r], L: r, R: r})
}
segments, newSegments = newSegments, segments
for i := 0; i < len(segments); i++ {
seg := segments[i]
for r-seg.L+1 > ans {
R_limit := r - ans
if R_limit > seg.R {
R_limit = seg.R
}
if exists(seg.L-1, R_limit-1, X[r], seg.val) {
ans++
} else {
break
}
}
}
}
fmt.Println(ans)
}