For problem statement at 1000-1999/1300-1399/1310-1319/1311/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1310-1319/1311/verifierE.go ends with test 6 failed
expected:
YES
1 2 2 3 3 5 5 6 6
got:
YES
1 1 2 2 4 4 6 8 9
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var t int
fmt.Fscan(reader, &t)
for i := 0; i < t; i++ {
var n, d int
fmt.Fscan(reader, &n, &d)
minD := 0
rem := n - 1
for h := 1; rem > 0; h++ {
c := 1 << h
if c > rem {
c = rem
}
minD += c * h
rem -= c
}
maxD := n * (n - 1) / 2
if d < minD || d > maxD {
fmt.Fprintln(writer, "NO")
continue
}
cnt := make([]int, n)
for j := 0; j < n; j++ {
cnt[j] = 1
}
S := maxD
L := n - 1
target := 1
for S > d {
for target < L && cnt[target] >= 2*cnt[target-1] {
target++
}
if S-d >= L-target {
S -= L - target
cnt[L]--
cnt[target]++
for L > 0 && cnt[L] == 0 {
L--
}
} else {
movTo := L - (S - d)
S = d
cnt[L]--
cnt[movTo]++
}
}
fmt.Fprintln(writer, "YES")
parent := make([]int, n+1)
nodes := make([][]int, n)
nodes[0] = []int{1}
id := 2
for h := 1; h < n; h++ {
for j := 0; j < cnt[h]; j++ {
p := nodes[h-1][j/2]
parent[id] = p
nodes[h] = append(nodes[h], id)
id++
}
}
for j := 2; j <= n; j++ {
if j > 2 {
fmt.Fprint(writer, " ")
}
fmt.Fprint(writer, parent[j])
}
fmt.Fprintln(writer)
}
}