For problem statement at 1000-1999/1600-1699/1650-1659/1658/problemD2.txt this is a correct solution, but verifier at 1000-1999/1600-1699/1650-1659/1658/verifierD2.go ends with All tests passed can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"os"
)
type FastScanner struct {
r *bufio.Reader
}
func NewFastScanner() *FastScanner {
return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}
func (fs *FastScanner) NextInt() int {
sign, val := 1, 0
c, _ := fs.r.ReadByte()
for (c < '0' || c > '9') && c != '-' {
c, _ = fs.r.ReadByte()
}
if c == '-' {
sign = -1
c, _ = fs.r.ReadByte()
}
for c >= '0' && c <= '9' {
val = val*10 + int(c-'0')
c2, err := fs.r.ReadByte()
if err != nil {
return sign * val
}
c = c2
}
fs.r.UnreadByte()
return sign * val
}
func partition(vals []int, bit int) int {
mask := 1 << bit
i, j := 0, len(vals)-1
for i <= j {
for i <= j && (vals[i]&mask) == 0 {
i++
}
for i <= j && (vals[j]&mask) != 0 {
j--
}
if i < j {
vals[i], vals[j] = vals[j], vals[i]
i++
j--
}
}
return i
}
func sameBit(vals []int, bit int) (int, bool) {
mask := 1 << bit
tb := 0
if (vals[0] & mask) != 0 {
tb = 1
}
for i := 1; i < len(vals); i++ {
if ((vals[i] & mask) != 0) != (tb == 1) {
return 0, false
}
}
return tb, true
}
func intersect(rep1, free1, rep2, free2 int) (int, int, bool) {
if free1 < free2 {
if (rep1 >> free2) == (rep2 >> free2) {
return rep1, free1, true
}
return 0, 0, false
}
if free2 < free1 {
if (rep2 >> free1) == (rep1 >> free1) {
return rep2, free2, true
}
return 0, 0, false
}
if rep1 == rep2 {
return rep1, free1, true
}
return 0, 0, false
}
func solveChain(bit, l, r int, vals []int) (int, int, bool) {
if bit < 0 {
return 0, 0, true
}
fullLen := 1 << (bit + 1)
if l == 0 && r == fullLen-1 {
return 0, bit + 1, true
}
m := 1 << bit
lb := (l >> bit) & 1
rb := (r >> bit) & 1
if lb == rb {
tb, ok := sameBit(vals, bit)
if !ok {
return 0, 0, false
}
xbit := tb ^ lb
rep, free, ok := solveChain(bit-1, l&(m-1), r&(m-1), vals)
if !ok {
return 0, 0, false
}
return rep | (xbit << bit), free, true
}
cnt0 := partition(vals, bit)
a0 := vals[:cnt0]
a1 := vals[cnt0:]
if l == 0 {
if cnt0 == m {
rep, free, ok := solveChain(bit-1, 0, r-m, a1)
if !ok {
return 0, 0, false
}
return rep, free, true
}
if len(a1) == m {
rep, free, ok := solveChain(bit-1, 0, r-m, a0)
if !ok {
return 0, 0, false
}
return rep | (1 << bit), free, true
}
return 0, 0, false
}
if len(a1) == m {
rep, free, ok := solveChain(bit-1, l, m-1, a0)
if !ok {
return 0, 0, false
}
return rep, free, true
}
if cnt0 == m {
rep, free, ok := solveChain(bit-1, l, m-1, a1)
if !ok {
return 0, 0, false
}
return rep | (1 << bit), free, true
}
return 0, 0, false
}
func solveAny(bit, l, r int, vals []int) int {
ans := 0
for bit >= 0 {
fullLen := 1 << (bit + 1)
if l == 0 && r == fullLen-1 {
return ans
}
m := 1 << bit
lb := (l >> bit) & 1
rb := (r >> bit) & 1
if lb != rb {
break
}
tb, _ := sameBit(vals, bit)
xbit := tb ^ lb
ans |= xbit << bit
l &= m - 1
r &= m - 1
bit--
}
if bit < 0 {
return ans
}
fullLen := 1 << (bit + 1)
if l == 0 && r == fullLen-1 {
return ans
}
if l == 0 || r == fullLen-1 {
rep, _, _ := solveChain(bit, l, r, vals)
return ans | rep
}
m := 1 << bit
cnt0 := partition(vals, bit)
a0 := vals[:cnt0]
a1 := vals[cnt0:]
n0 := m - l
n1 := r - m + 1
if cnt0 == n0 && len(a1) == n1 {
repL, freeL, okL := solveChain(bit-1, l, m-1, a0)
if okL {
repR, freeR, okR := solveChain(bit-1, 0, r-m, a1)
if okR {
rep, _, ok := intersect(repL, freeL, repR, freeR)
if ok {
return ans | rep
}
}
}
}
if cnt0 == n1 && len(a1) == n0 {
repL, freeL, okL := solveChain(bit-1, l, m-1, a1)
if okL {
repR, freeR, okR := solveChain(bit-1, 0, r-m, a0)
if okR {
rep, _, ok := intersect(repL, freeL, repR, freeR)
if ok {
return ans | (1 << bit) | rep
}
}
}
}
return ans
}
func main() {
in := NewFastScanner()
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
t := in.NextInt()
for ; t > 0; t-- {
l := in.NextInt()
r := in.NextInt()
n := r - l + 1
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = in.NextInt()
}
ans := solveAny(16, l, r, a)
fmt.Fprintln(out, ans)
}
}
```