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