For problem statement at 1000-1999/1800-1899/1860-1869/1868/problemD.txt this is a correct solution, but verifier at 1000-1999/1800-1899/1860-1869/1868/verifierD.go ends with case 71 failed: reference failed: runtime error: exit status 2
panic: runtime error: index out of range [-1]
goroutine 1 [running]:
main.solve.func2(...)
/home/ubuntu/codeforces/1000-1999/1800-1899/1860-1869/1868/1868D.go:47
main.solve()
/home/ubuntu/codeforces/1000-1999/1800-1899/1860-1869/1868/1868D.go:134 +0xd24
main.main()
/home/ubuntu/codeforces/1000-1999/1800-1899/1860-1869/1868/1868D.go:153 +0xb0
input:
1
6
3 0 3 2 3 1
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"sort"
)
type Node struct {
id, deg int
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var t int
if _, err := fmt.Fscan(in, &t); err != nil {
return
}
for tc := 0; tc < t; tc++ {
var n int
fmt.Fscan(in, &n)
dIn := make([]int, n)
sumDeg := int64(0)
var S_3, S_2, S_1 []Node
for i := 0; i < n; i++ {
fmt.Fscan(in, &dIn[i])
sumDeg += int64(dIn[i])
if dIn[i] >= 3 {
S_3 = append(S_3, Node{i + 1, dIn[i]})
} else if dIn[i] == 2 {
S_2 = append(S_2, Node{i + 1, dIn[i]})
} else if dIn[i] == 1 {
S_1 = append(S_1, Node{i + 1, dIn[i]})
}
}
if sumDeg != int64(2*n) {
fmt.Fprintln(out, "No")
continue
}
if len(S_3) == 0 {
fmt.Fprintln(out, "Yes")
for i := 1; i <= n; i++ {
v := i + 1
if v > n {
v = 1
}
fmt.Fprintln(out, i, v)
}
continue
}
if len(S_3) == 1 {
fmt.Fprintln(out, "No")
continue
}
sort.Slice(S_3, func(i, j int) bool {
return S_3[i].deg > S_3[j].deg
})
A := make([]Node, 0, len(S_3)+len(S_2))
A = append(A, S_3...)
A = append(A, S_2...)
pref_A := make([]int, len(A)+1)
for i := 0; i < len(A); i++ {
pref_A[i+1] = pref_A[i] + A[i].deg - 1
}
pref_roots := make([]int, len(S_3)+1)
for i := 0; i < len(S_3); i++ {
pref_roots[i+1] = pref_roots[i] + S_3[i].deg - 2
}
found := false
var bestC, bestD int
for C := len(S_3); C >= 2; C-- {
I := len(A) - C
if I == 0 {
found = true
bestC = C
bestD = 0
break
}
Pc := pref_roots[C]
rem := I
cap := Pc
idx := 0
Lmin := 0
possible := true
for rem > 0 {
if cap == 0 {
possible = false
break
}
take := cap
if take > rem {
take = rem
}
start := C + idx
end := C + idx + take
if A[start].deg == 2 {
steps := rem / cap
Lmin += steps
if rem%cap > 0 {
Lmin++
}
break
}
nextCap := pref_A[end] - pref_A[start]
cap = nextCap
rem -= take
idx += take
Lmin++
}
if possible && Lmin <= I/C {
found = true
bestC = C
bestD = Lmin
break
}
}
if !found {
fmt.Fprintln(out, "No")
continue
}
fmt.Fprintln(out, "Yes")
C := bestC
D := bestD
I := len(A) - C
counts := make([]int, D)
for i := 0; i < D; i++ {
counts[i] = C
}
rem := I - C*D
currCap := pref_roots[C]
idx := 0
for d := 0; d < D; d++ {
add := rem
if add > currCap-C {
add = currCap - C
}
counts[d] += add
rem -= add
start := C + idx
end := C + idx + counts[d]
currCap = pref_A[end] - pref_A[start]
idx += counts[d]
}
for i := 0; i < C; i++ {
u := S_3[i].id
v := S_3[(i+1)%C].id
fmt.Fprintln(out, u, v)
}
mand := make([][]int, C)
var opt []int
for i := 0; i < C; i++ {
u := S_3[i]
mand[i] = append(mand[i], u.id)
for p := 0; p < u.deg-3; p++ {
opt = append(opt, u.id)
}
}
idx = 0
for d := 0; d < D; d++ {
take := counts[d]
for i := 0; i < C; i++ {
v := A[C+idx]
idx++
u := mand[i][0]
fmt.Fprintln(out, u, v.id)
mand[i][0] = v.id
for p := 0; p < v.deg-2; p++ {
opt = append(opt, v.id)
}
}
for j := 0; j < take-C; j++ {
v := A[C+idx]
idx++
u := opt[len(opt)-1]
opt = opt[:len(opt)-1]
fmt.Fprintln(out, u, v.id)
for p := 0; p < v.deg-1; p++ {
opt = append(opt, v.id)
}
}
}
leafIdx := 0
for i := 0; i < C; i++ {
u := mand[i][0]
v := S_1[leafIdx]
leafIdx++
fmt.Fprintln(out, u, v.id)
}
for i := 0; i < len(opt); i++ {
u := opt[i]
v := S_1[leafIdx]
leafIdx++
fmt.Fprintln(out, u, v.id)
}
}
}