For problem statement at 0-999/100-199/130-139/134/problemC.txt this is a correct solution, but verifier at 0-999/100-199/130-139/134/verifierC.go ends with Test 24 failed.
Input:
1 10
0
Expected:
Yes
0
Got:
No
exit status 1 can you fix the verifier? package main
import (
"bufio"
"container/heap"
"os"
"strconv"
)
type Item struct {
id int
deg int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].deg > pq[j].deg
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(*Item))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil
*pq = old[0 : n-1]
return item
}
type Scanner struct {
buf []byte
head int
tail int
f *os.File
}
func NewScanner(f *os.File) *Scanner {
return &Scanner{
buf: make([]byte, 1<<16),
f: f,
}
}
func (s *Scanner) NextInt() int {
var res int
for {
if s.head >= s.tail {
s.head = 0
s.tail, _ = s.f.Read(s.buf)
if s.tail == 0 {
return res
}
}
if s.buf[s.head] >= '0' && s.buf[s.head] <= '9' {
break
}
s.head++
}
for {
if s.head >= s.tail {
s.head = 0
s.tail, _ = s.f.Read(s.buf)
if s.tail == 0 {
return res
}
}
if s.buf[s.head] < '0' || s.buf[s.head] > '9' {
break
}
res = res*10 + int(s.buf[s.head]-'0')
s.head++
}
return res
}
func main() {
sc := NewScanner(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
n := sc.NextInt()
s := sc.NextInt()
pq := make(PriorityQueue, 0, n)
sum := 0
for i := 1; i <= n; i++ {
deg := sc.NextInt()
if deg > 0 {
pq = append(pq, &Item{id: i, deg: deg})
sum += deg
}
}
if sum%2 != 0 || sum != s {
out.WriteString("No\n")
return
}
heap.Init(&pq)
type Edge struct {
u, v int
}
edges := make([]Edge, 0, sum/2)
for pq.Len() > 0 {
u := heap.Pop(&pq).(*Item)
d := u.deg
if d == 0 {
continue
}
if pq.Len() < d {
out.WriteString("No\n")
return
}
popped := make([]*Item, d)
for i := 0; i < d; i++ {
popped[i] = heap.Pop(&pq).(*Item)
}
for i := 0; i < d; i++ {
v := popped[i]
edges = append(edges, Edge{u.id, v.id})
v.deg--
}
for i := 0; i < d; i++ {
if popped[i].deg > 0 {
heap.Push(&pq, popped[i])
}
}
}
out.WriteString("Yes\n")
out.WriteString(strconv.Itoa(len(edges)) + "\n")
for _, e := range edges {
out.WriteString(strconv.Itoa(e.u) + " " + strconv.Itoa(e.v) + "\n")
}
}