For problem statement at 0-999/0-99/0-9/6/problemD.txt this is a correct solution, but verifier at 0-999/0-99/0-9/6/verifierD.go ends with case 72 failed: expected
5
2 2 4 4 4
got
5
2 3 4 4 4
input:
5 3 2
1 4 3 3 4
exit status 1 can you fix the verifier? ```go
package main
import (
"fmt"
)
const MAX_X = 30
const INF = 1<<30
const MAX_C = 600
type Config struct {
T int
Dmg [11]int
Counts []int
}
type Node struct {
t int
idx int
}
var N, A, B int
var H [11]int
var D [11]int
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func generateConfigs(pos []int, affected_other [11]bool) []Config {
var result []Config
var rec func(int, [11]int, int, []int)
rec = func(idx int, dmg [11]int, t int, counts []int) {
if idx == len(pos) {
valid := true
for i := 1; i <= N; i++ {
if !affected_other[i] && dmg[i] < D[i] {
valid = false
break
}
}
if valid {
c := Config{T: t, Dmg: dmg}
c.Counts = make([]int, len(counts))
copy(c.Counts, counts)
result = append(result, c)
}
return
}
hit := pos[idx]
for x := 0; x <= MAX_X; x++ {
var new_dmg = dmg
if hit-1 >= 1 {
new_dmg[hit-1] += x * B
}
new_dmg[hit] += x * A
if hit+1 <= N {
new_dmg[hit+1] += x * B
}
new_counts := make([]int, len(counts))
copy(new_counts, counts)
new_counts[idx] = x
rec(idx+1, new_dmg, t+x, new_counts)
}
}
var initial [11]int
rec(0, initial, 0, make([]int, len(pos)))
return result
}
func main() {
fmt.Scan(&N, &A, &B)
for i := 1; i <= N; i++ {
fmt.Scan(&H[i])
D[i] = H[i] + 1
}
var hits []int
for i := 2; i <= N-1; i++ {
hits = append(hits, i)
}
m := len(hits)
l := m / 2
left_pos := hits[:l]
right_pos := hits[l:]
var affected_left [11]bool
for _, p := range left_pos {
if p-1 >= 1 {
affected_left[p-1] = true
}
affected_left[p] = true
if p+1 <= N {
affected_left[p+1] = true
}
}
var affected_right [11]bool
for _, p := range right_pos {
if p-1 >= 1 {
affected_right[p-1] = true
}
affected_right[p] = true
if p+1 <= N {
affected_right[p+1] = true
}
}
var overlap []int
for i := 1; i <= N; i++ {
if affected_left[i] && affected_right[i] {
overlap = append(overlap, i)
}
}
left_configs := generateConfigs(left_pos, affected_right)
right_configs := generateConfigs(right_pos, affected_left)
minT := INF
bestLeft := -1
bestRight := -1
numLeft := len(left_configs)
numRight := len(right_configs)
if numLeft*numRight <= 100000000 {
for li := 0; li < numLeft; li++ {
lc := left_configs[li]
for ri := 0; ri < numRight; ri++ {
rc := right_configs[ri]
valid := true
for i := 1; i <= N; i++ {
if lc.Dmg[i]+rc.Dmg[i] < D[i] {
valid = false
break
}
}
if valid {
tot := lc.T + rc.T
if tot < minT {
minT = tot
bestLeft = li
bestRight = ri
}
}
}
}
} else {
if len(overlap) != 2 {
return
}
contribIdx1 := overlap[0]
contribIdx2 := overlap[1]
min_t := make([][]Node, MAX_C+1)
for i := 0; i <= MAX_C; i++ {
min_t[i] = make([]Node, MAX_C+1)
for j := 0; j <= MAX_C; j++ {
min_t[i][j].t = INF
min_t[i][j].idx = -1
}
}
for ri := 0; ri < numRight; ri++ {
rc := right_configs[ri]
c1 := rc.Dmg[contribIdx1]
c2 := rc.Dmg[contribIdx2]
if c1 > MAX_C {
c1 = MAX_C
}
if c2 > MAX_C {
c2 = MAX_C
}
if rc.T < min_t[c1][c2].t {
min_t[c1][c2].t = rc.T
min_t[c1][c2].idx = ri
}
}
for x := MAX_C; x >= 0; x-- {
for y := MAX_C; y >= 0; y-- {
candidates := []Node{min_t[x][y]}
if x < MAX_C {
candidates = append(candidates, min_t[x+1][y])
}
if y < MAX_C {
candidates = append(candidates, min_t[x][y+1])
}
minVal := INF
var bestNode Node
for _, cand := range candidates {
if cand.t < minVal {
minVal = cand.t
bestNode = cand
}
}
min_t[x][y].t = minVal
min_t[x][y].idx = bestNode.idx
}
}
for li := 0; li < numLeft; li++ {
lc := left_configs[li]
need1 := max(0, D[contribIdx1]-lc.Dmg[contribIdx1])
need2 := max(0, D[contribIdx2]-lc.Dmg[contribIdx2])
node := min_t[need1][need2]
if node.t < INF {
tot := lc.T + node.t
if tot < minT {
minT = tot
bestLeft = li
bestRight = node.idx
}
}
}
}
if minT == INF {
return
}
var list []int
lc := left_configs[bestLeft]
for j := 0; j < len(left_pos); j++ {
p := left_pos[j]
for k := 0; k < lc.Counts[j]; k++ {
list = append(list, p)
}
}
rc := right_configs[bestRight]
for j := 0; j < len(right_pos); j++ {
p := right_pos[j]
for k := 0; k < rc.Counts[j]; k++ {
list = append(list, p)
}
}
fmt.Println(minT)
for i, idx := range list {
if i > 0 {
fmt.Print(" ")
}
fmt.Print(idx)
}
fmt.Println()
}
```