← Home
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)
}