For problem statement at 0-999/300-399/350-359/356/problemE.txt this is a correct solution, but verifier at 0-999/300-399/350-359/356/verifierE.go ends with test 1 failed
input:
mzsxiif
expected:
7
got:
16
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"math/bits"
"os"
)
var (
chars []byte
lens []int
ids [][]int
g []int64
)
func diff1(level, s1, s2 int) (int, int, byte, byte) {
off := 0
for {
if ids[level][s1] == ids[level][s2] {
return 0, 0, 0, 0
}
if level == 0 {
return 1, off, chars[s1], chars[s2]
}
lp := lens[level-1]
neq := 0
comp := 0
if ids[level-1][s1] != ids[level-1][s2] {
neq++
comp = 1
}
if chars[s1+lp] != chars[s2+lp] {
neq++
comp = 2
}
if ids[level-1][s1+lp+1] != ids[level-1][s2+lp+1] {
neq++
comp = 3
}
if neq > 1 {
return 2, 0, 0, 0
}
if comp == 2 {
return 1, off + lp, chars[s1+lp], chars[s2+lp]
}
level--
if comp == 3 {
s1 += lp + 1
s2 += lp + 1
off += lp + 1
}
}
}
func addMask(pos int, mask uint32, w int64) {
base := pos * 26
for mask != 0 {
b := bits.TrailingZeros32(mask)
g[base+b] += w
mask &= mask - 1
}
}
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
var s string
fmt.Fscan(in, &s)
n := len(s)
chars = make([]byte, n)
for i := 0; i < n; i++ {
chars[i] = s[i] - 'a'
}
for x := 1; x <= n; x = x*2 + 1 {
lens = append(lens, x)
}
ids = make([][]int, len(lens))
g = make([]int64, n*26)
diff := make([]int64, n+1)
ids[0] = make([]int, n)
maskPrev := make([]uint32, n)
var beauty int64
const allMask uint32 = (1 << 26) - 1
for i := 0; i < n; i++ {
c := chars[i]
ids[0][i] = int(c) + 1
maskPrev[i] = uint32(1) << c
beauty++
diff[i]++
diff[i+1]--
base := i * 26
for ch := 0; ch < 26; ch++ {
if ch != int(c) {
g[base+ch]++
}
}
}
for level := 1; level < len(lens); level++ {
lp := lens[level-1]
lc := lens[level]
m := n - lc + 1
idPrev := ids[level-1]
idCur := make([]int, m)
ids[level] = idCur
maskCur := make([]uint32, m)
mp := make(map[uint64]int, m*2)
nextID := 1
w := int64(lc) * int64(lc)
for st := 0; st < m; st++ {
right := st + lp + 1
key := (uint64(idPrev[st]) << 22) | (uint64(chars[st+lp]) << 17) | uint64(idPrev[right])
if v, ok := mp[key]; ok {
idCur[st] = v
} else {
idCur[st] = nextID
mp[key] = nextID
nextID++
}
centerPos := st + lp
centerBit := uint32(1) << chars[centerPos]
if idPrev[st] == idPrev[right] {
childMask := maskPrev[st]
if childMask != 0 {
if childMask¢erBit == 0 {
maskCur[st] = childMask | centerBit
beauty += w
diff[st] += w
diff[st+lc] -= w
}
allowed := allMask ^ childMask
if childMask¢erBit == 0 {
allowed &^= centerBit
}
if allowed != 0 {
addMask(centerPos, allowed, w)
}
}
} else {
stt, off, cl, cr := diff1(level-1, st, right)
if stt == 1 {
childMask := maskPrev[right]
if childMask != 0 && childMask¢erBit == 0 {
g[(st+off)*26+int(cr)] += w
}
childMask = maskPrev[st]
if childMask != 0 && childMask¢erBit == 0 {
g[(right+off)*26+int(cl)] += w
}
}
}
}
maskPrev = maskCur
}
ans := beauty
var cover int64
for i := 0; i < n; i++ {
cover += diff[i]
base := i * 26
orig := int(chars[i])
for c := 0; c < 26; c++ {
if c == orig {
continue
}
v := beauty - cover + g[base+c]
if v > ans {
ans = v
}
}
}
out := bufio.NewWriterSize(os.Stdout, 1<<20)
fmt.Fprint(out, ans)
out.Flush()
}
```