For problem statement at 1000-1999/1700-1799/1780-1789/1784/problemE.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1780-1789/1784/verifierE.go ends with All tests passed. can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
func getTrans() ([4][2]int, [4][2]int) {
var f [4][2]int
var W [4][2]int
f[0][0] = 1
W[0][0] = 0
f[0][1] = 2
W[0][1] = 0
f[1][0] = 0
W[1][0] = 1
f[1][1] = 3
W[1][1] = 0
f[2][0] = 3
W[2][0] = 0
f[2][1] = 0
W[2][1] = -1
f[3][0] = 0
W[3][0] = 1
f[3][1] = 0
W[3][1] = -1
return f, W
}
func packCore(f0, f1, f2, f3 int8, d1, d2, d3 int16) uint64 {
var res uint64
res |= uint64(f0)
res |= uint64(f1) << 2
res |= uint64(f2) << 4
res |= uint64(f3) << 6
res |= uint64(uint16(d1)) << 8
res |= uint64(uint16(d2)) << 24
res |= uint64(uint16(d3)) << 40
return res
}
func unpackCore(res uint64) (f0, f1, f2, f3 int8, d1, d2, d3 int16) {
f0 = int8(res & 3)
f1 = int8((res >> 2) & 3)
f2 = int8((res >> 4) & 3)
f3 = int8((res >> 6) & 3)
d1 = int16(res >> 8)
d2 = int16(res >> 24)
d3 = int16(res >> 40)
return
}
type Trans struct {
id int
shift int
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
if !scanner.Scan() {
return
}
s := scanner.Text()
f_trans, W_trans := getTrans()
stateToID := make(map[uint64]int)
var idToState []uint64
var transitions [][2]Trans
getID := func(state uint64) int {
if id, exists := stateToID[state]; exists {
return id
}
id := len(stateToID)
stateToID[state] = id
idToState = append(idToState, state)
transitions = append(transitions, [2]Trans{{-1, 0}, {-1, 0}})
return id
}
OFFSET := 300
MAXW := 600
MOD := 998244353
startState := packCore(0, 1, 2, 3, 0, 0, 0)
startID := getID(startState)
dp := make([][]int, startID+1)
dp[startID] = make([]int, MAXW)
dp[startID][OFFSET] = 1
for i := 0; i < len(s); i++ {
chars := []int{0, 1}
if s[i] == 'a' {
chars = []int{0}
} else if s[i] == 'b' {
chars = []int{1}
}
next_dp := make([][]int, len(stateToID))
for id := 0; id < len(dp); id++ {
if dp[id] == nil {
continue
}
for _, c := range chars {
if transitions[id][c].id == -1 {
f0, f1, f2, f3, d1, d2, d3 := unpackCore(idToState[id])
nf0 := f_trans[f0][c]
nf1 := f_trans[f1][c]
nf2 := f_trans[f2][c]
nf3 := f_trans[f3][c]
shift := W_trans[f0][c]
nd1 := d1 + int16(W_trans[f1][c]) - int16(shift)
nd2 := d2 + int16(W_trans[f2][c]) - int16(shift)
nd3 := d3 + int16(W_trans[f3][c]) - int16(shift)
nstate := packCore(int8(nf0), int8(nf1), int8(nf2), int8(nf3), nd1, nd2, nd3)
nid := getID(nstate)
transitions[id][c] = Trans{id: nid, shift: shift}
}
trans := transitions[id][c]
nid := trans.id
shift := trans.shift
for len(next_dp) <= nid {
next_dp = append(next_dp, nil)
}
if next_dp[nid] == nil {
next_dp[nid] = make([]int, MAXW)
}
for w0 := 0; w0 < MAXW; w0++ {
if cnt := dp[id][w0]; cnt > 0 {
next_dp[nid][w0+shift] = (next_dp[nid][w0+shift] + cnt) % MOD
}
}
}
}
dp = next_dp
}
ansA, ansTie, ansBob := 0, 0, 0
for id := 0; id < len(dp); id++ {
if dp[id] == nil {
continue
}
f0, f1, f2, f3, d1, d2, d3 := unpackCore(idToState[id])
visited := make([]int, 4)
for i := range visited {
visited[i] = -1
}
curr := 0
path := []int{}
for visited[curr] == -1 {
visited[curr] = len(path)
path = append(path, curr)
switch curr {
case 0:
curr = int(f0)
case 1:
curr = int(f1)
case 2:
curr = int(f2)
case 3:
curr = int(f3)
}
}
startCycle := visited[curr]
cycleLen := len(path) - startCycle
cycleD := 0
for i := startCycle; i < len(path); i++ {
switch path[i] {
case 1:
cycleD += int(d1)
case 2:
cycleD += int(d2)
case 3:
cycleD += int(d3)
}
}
for w0 := 0; w0 < MAXW; w0++ {
if cnt := dp[id][w0]; cnt > 0 {
actualW0 := w0 - OFFSET
sumW := cycleLen*actualW0 + cycleD
if sumW > 0 {
ansA = (ansA + cnt) % MOD
} else if sumW < 0 {
ansBob = (ansBob + cnt) % MOD
} else {
ansTie = (ansTie + cnt) % MOD
}
}
}
}
fmt.Printf("%d %d %d\n", ansA, ansTie, ansBob)
}