← Home
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)
		}
	}
}