← Home
For problem statement at 1000-1999/1400-1499/1460-1469/1469/problemE.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1460-1469/1469/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

var seen = make([]int, 1<<20)
var ones = make([]int, 1000005)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)

	for tc := 1; tc <= t; tc++ {
		var n, k int
		fmt.Fscan(reader, &n, &k)
		var s string
		fmt.Fscan(reader, &s)

		if s[0] == '1' {
			ones[0] = 1
		} else {
			ones[0] = 0
		}
		for i := 1; i < n; i++ {
			if s[i] == '1' {
				ones[i] = ones[i-1] + 1
			} else {
				ones[i] = 0
			}
		}

		m := k
		if m > 20 {
			m = 20
		}
		mask := (1 << m) - 1
		val := 0
		for j := 0; j < m; j++ {
			bit := 1 - int(s[k-m+j]-'0')
			val = (val << 1) | bit
		}

		for i := 0; i <= n-k; i++ {
			if k-m == 0 || ones[i+k-m-1] >= k-m {
				seen[val] = tc
			}
			if i < n-k {
				bit := 1 - int(s[i+k]-'0')
				val = ((val << 1) & mask) | bit
			}
		}

		found := false
		for v := 0; v < (1<<m); v++ {
			if seen[v] != tc {
				fmt.Fprintln(writer, "YES")
				buf := make([]byte, k)
				for i := 0; i < k-m; i++ {
					buf[i] = '0'
				}
				for i := 0; i < m; i++ {
					if (v & (1 << (m - 1 - i))) != 0 {
						buf[k-m+i] = '1'
					} else {
						buf[k-m+i] = '0'
					}
				}
				fmt.Fprintln(writer, string(buf))
				found = true
				break
			}
		}
		if !found {
			fmt.Fprintln(writer, "NO")
		}
	}
}