For problem statement at 0-999/900-999/960-969/961/problemF.txt this is a correct solution, but verifier at 0-999/900-999/960-969/961/verifierF.go ends with Test 84 failed
Input:
21
gloqjybgxtotgnvggpryn
Expected: -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1
Got: -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
type Hasher struct {
n int
base uint64
pow []uint64
pre []uint64
}
func NewHasher(s []byte, base uint64) *Hasher {
n := len(s)
h := &Hasher{
n: n,
base: base,
pow: make([]uint64, n+1),
pre: make([]uint64, n+1),
}
h.pow[0] = 1
var b = base
for i := 0; i < n; i++ {
h.pow[i+1] = h.pow[i] * b
h.pre[i+1] = h.pre[i]*b + uint64(s[i]-'a'+1)
}
return h
}
func (h *Hasher) get(l, r int) uint64 {
// returns hash of s[l..r]
return h.pre[r+1] - h.pre[l]*h.pow[r-l+1]
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n)
var s string
fmt.Fscan(in, &s)
b := []byte(s)
h1 := NewHasher(b, 146527)
h2 := NewHasher(b, 19260817)
total := (n + 1) / 2
for k := 0; k < total; k++ {
u := k
m := n - 1 - k
L := m - u + 1
if L == 1 {
if k > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, -1)
continue
}
maxT := (L - 1) / 2
// Binary search the largest t in [0..maxT] such that
// s[u..u+(2t+1)-1] == s[m-(2t+1)+1 .. m]
lo, hi := 0, maxT
best := -1
for lo <= hi {
mid := (lo + hi) >> 1
l := 2*mid + 1
lhs1 := h1.get(u, u+l-1)
rhs1 := h1.get(m-l+1, m)
if lhs1 == rhs1 {
lhs2 := h2.get(u, u+l-1)
rhs2 := h2.get(m-l+1, m)
if lhs2 == rhs2 {
best = mid
lo = mid + 1
continue
}
}
hi = mid - 1
}
if k > 0 {
fmt.Fprint(out, " ")
}
if best >= 0 {
fmt.Fprint(out, 2*best+1)
} else {
fmt.Fprint(out, -1)
}
}
}