For problem statement at 1000-1999/1300-1399/1390-1399/1392/problemG.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1390-1399/1392/verifierG.go ends with All tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"io"
"math/bits"
"os"
)
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) skip() {
for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
fs.idx++
}
}
func (fs *FastScanner) Int() int {
fs.skip()
sign := 1
if fs.idx < fs.n && 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 (fs *FastScanner) String() string {
fs.skip()
start := fs.idx
for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
fs.idx++
}
return string(fs.data[start:fs.idx])
}
func maskFromString(s string) uint32 {
var m uint32
for i := 0; i < len(s); i++ {
if s[i] == '1' {
m |= 1 << uint(i)
}
}
return m
}
func insertSource(src uint32, idx int32, dist []uint8, owner []int32, queue []uint32, bitMasks []uint32) {
s := int(src)
if dist[s] == 0 {
return
}
dist[s] = 0
owner[s] = idx
queue[0] = src
head, tail := 0, 1
for head < tail {
cur := queue[head]
head++
ci := int(cur)
nd := dist[ci] + 1
own := owner[ci]
for j := 0; j < len(bitMasks); j++ {
nxt := cur ^ bitMasks[j]
ni := int(nxt)
if nd < dist[ni] {
dist[ni] = nd
owner[ni] = own
queue[tail] = nxt
tail++
}
}
}
}
func main() {
fs := NewFastScanner()
n := fs.Int()
m := fs.Int()
k := fs.Int()
xMask := maskFromString(fs.String())
yMask := maskFromString(fs.String())
U := make([]uint32, n+1)
U[0] = xMask
pos := make([]int, k)
for i := 0; i < k; i++ {
pos[i] = i
}
size := 1 << k
dist := make([]uint8, size)
owner := make([]int32, size)
queue := make([]uint32, size)
bitMasks := make([]uint32, k)
for i := 0; i < k; i++ {
bitMasks[i] = 1 << uint(i)
}
curU := xMask
curV := yMask
bestS := -1
bestL, bestR := 1, m
for i := 1; i <= n; i++ {
a := fs.Int() - 1
b := fs.Int() - 1
pa := pos[a]
pb := pos[b]
bitA := uint32(1) << uint(pa)
bitB := uint32(1) << uint(pb)
if ((curU>>uint(pa))^(curU>>uint(pb)))&1 != 0 {
curU ^= bitA | bitB
}
if ((curV>>uint(pa))^(curV>>uint(pb)))&1 != 0 {
curV ^= bitA | bitB
}
pos[a], pos[b] = pb, pa
U[i] = curU
if i == m {
src := U[0]
for mask := 0; mask < size; mask++ {
dist[mask] = uint8(bits.OnesCount32(uint32(mask) ^ src))
}
} else if i > m {
insertSource(U[i-m], int32(i-m), dist, owner, queue, bitMasks)
}
if i >= m {
vi := int(curV)
score := k - int(dist[vi])
if score > bestS {
bestS = score
bestL = int(owner[vi]) + 1
bestR = i
}
}
}
w := bufio.NewWriterSize(os.Stdout, 1<<20)
fmt.Fprintln(w, bestS)
fmt.Fprintln(w, bestL, bestR)
w.Flush()
}