For problem statement at 0-999/800-899/850-859/850/problemD.txt this is a correct solution, but verifier at 0-999/800-899/850-859/850/verifierD.go ends with Test 1 failed
Input:
5
19 12 0 21 26
Expected:
27
000000000000000000000000000
100000000000111111111100100
110000000000111111111000100
111000000000111111110001000
111100000000111111100001000
111110000000111111000001000
111111000000000001111110000
111111101111100000000000000
111111100111110000000000000
111111100011111000000000000
111111100001111100000000000
111111100000111110000000000
100000100000011111111110000
100000110000001111111110000
100000111000000111111110000
100000111100000011111110000
100000111110000001111110000
100000011111000000111111000
100001011111000000011111000
100011011111000000001111000
100111011111000000000110100
101111011111000000000010010
111111011111000000000000010
111000111111111110001110110
100111111111111111110110010
111111111111111111111000000
111111111111111111111111110
Got:
27
000000000000000000000000000
101111111111100000000000000
100111111111101000000000000
100011111111111000000000000
100001111111111000100000000
100000111111111110000000000
100000011111111100101000000
100000001111111111100000000
100000000111111111101000000
100000000011111111111000000
100000000001111111111001000
100000000000111111111110000
100000000000011111111111000
111000000000001111111110000
110000000000000111111111100
111110000000000011111110000
111110100000000001111110000
111111100000000000111110000
111101000000000000011111110
111111111000000000001110000
111111010000000000000111110
111111111110000000000010000
111111111110000000000001000
111111111101010111010100110
111111111111110111010110010
111111111111111111010110000
111111111111111111111111110
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"os"
"sort"
)
type Node struct {
deg int
id int
}
var mat [][]byte
func comb2(x int) int {
return x * (x - 1) / 2
}
func hasBit(bs []uint64, pos int) bool {
return ((bs[pos>>6] >> uint(pos&63)) & 1) != 0
}
func shiftOr(src, dst []uint64, shift int) {
ws := shift >> 6
bs := uint(shift & 63)
if bs == 0 {
for i, v := range src {
if v == 0 {
continue
}
j := i + ws
if j < len(dst) {
dst[j] |= v
}
}
} else {
rb := 64 - bs
for i, v := range src {
if v == 0 {
continue
}
j := i + ws
if j < len(dst) {
dst[j] |= v << bs
}
if j+1 < len(dst) {
dst[j+1] |= v >> rb
}
}
}
}
func keepRange(bs []uint64, l, h int) {
if l < 0 {
l = 0
}
if h < l {
for i := range bs {
bs[i] = 0
}
return
}
for i := 0; i < len(bs); i++ {
lo := i * 64
hi := lo + 63
if hi < l || lo > h {
bs[i] = 0
continue
}
mask := ^uint64(0)
if l > lo {
start := uint(l - lo)
mask &= ^((uint64(1) << start) - 1)
}
if h < hi {
end := uint(h - lo + 1)
mask &= (uint64(1) << end) - 1
}
bs[i] &= mask
}
}
func build(nodes []Node) {
if len(nodes) <= 1 {
return
}
sort.Slice(nodes, func(i, j int) bool {
if nodes[i].deg != nodes[j].deg {
return nodes[i].deg < nodes[j].deg
}
return nodes[i].id < nodes[j].id
})
v := nodes[0]
d := v.deg
rem := make([]Node, len(nodes)-1)
for i := 1; i < len(nodes); i++ {
rem[i-1] = nodes[i]
if i-1 < d {
mat[v.id][nodes[i].id] = '1'
} else {
mat[nodes[i].id][v.id] = '1'
rem[i-1].deg--
}
}
build(rem)
}
func solve(scores []int) (int, []int, bool) {
m := len(scores)
minScore := scores[0]
maxScore := scores[m-1]
prefix := make([]int, m+1)
for i := 0; i < m; i++ {
prefix[i+1] = prefix[i] + scores[i]
}
baseSum := prefix[m]
minN := m
if maxScore+1 > minN {
minN = maxScore + 1
}
if 2*minScore+1 > minN {
minN = 2*minScore + 1
}
maxN := 2*maxScore + 1
if maxN > 61 {
maxN = 61
}
if minN > maxN {
return 0, nil, false
}
for n := minN; n <= maxN; n++ {
r := n - m
total := comb2(n)
targetExtra := total - baseSum
if targetExtra < 0 {
continue
}
if targetExtra < r*minScore || targetExtra > r*maxScore {
continue
}
w := targetExtra/64 + 1
stride := (r + 1) * w
data := make([]uint64, (m+1)*stride)
data[0] = 1
for p := 0; p < m; p++ {
curBase := p * stride
nextBase := (p + 1) * stride
for i := 0; i < stride; i++ {
data[nextBase+i] = 0
}
score := scores[p]
for used := 0; used <= r; used++ {
srcStart := curBase + used*w
src := data[srcStart : srcStart+w]
nonZero := false
for _, v := range src {
if v != 0 {
nonZero = true
break
}
}
if !nonZero {
continue
}
for add := 0; add <= r-used; add++ {
shift := add * score
if score > 0 && shift > targetExtra {
break
}
dstStart := nextBase + (used+add)*w
shiftOr(src, data[dstStart:dstStart+w], shift)
}
}
for used := 0; used <= r; used++ {
bs := data[nextBase+used*w : nextBase+(used+1)*w]
if p+1 == m {
if used == r {
keepRange(bs, targetExtra, targetExtra)
} else {
for i := range bs {
bs[i] = 0
}
}
} else {
k := (p + 1) + used
l := comb2(k) - prefix[p+1]
rem := r - used
low := targetExtra - rem*maxScore
if low > l {
l = low
}
h := targetExtra - rem*scores[p+1]
if h > targetExtra {
h = targetExtra
}
keepRange(bs, l, h)
}
}
}
finalState := data[m*stride+r*w : m*stride+(r+1)*w]
if !hasBit(finalState, targetExtra) {
continue
}
extra := make([]int, m)
used := r
cur := targetExtra
ok := true
for p := m; p >= 1; p-- {
score := scores[p-1]
prevBase := (p - 1) * stride
found := false
for add := 0; add <= used; add++ {
prev := cur - add*score
if prev < 0 {
if score > 0 {
break
}
continue
}
bs := data[prevBase+(used-add)*w : prevBase+(used-add+1)*w]
if hasBit(bs, prev) {
extra[p-1] = add
used -= add
cur = prev
found = true
break
}
}
if !found {
ok = false
break
}
}
if !ok || used != 0 || cur != 0 {
continue
}
counts := make([]int, m)
for i := 0; i < m; i++ {
counts[i] = 1 + extra[i]
}
return n, counts, true
}
return 0, nil, false
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var m int
fmt.Fscan(in, &m)
scores := make([]int, m)
for i := 0; i < m; i++ {
fmt.Fscan(in, &scores[i])
}
sort.Ints(scores)
n, counts, ok := solve(scores)
if !ok {
fmt.Fprint(out, "=(")
return
}
degrees := make([]int, 0, n)
for i, s := range scores {
for j := 0; j < counts[i]; j++ {
degrees = append(degrees, s)
}
}
mat = make([][]byte, n)
for i := 0; i < n; i++ {
row := make([]byte, n)
for j := 0; j < n; j++ {
row[j] = '0'
}
mat[i] = row
}
nodes := make([]Node, n)
for i, d := range degrees {
nodes[i] = Node{deg: d, id: i}
}
build(nodes)
fmt.Fprintln(out, n)
for i := 0; i < n; i++ {
out.Write(mat[i])
out.WriteByte('\n')
}
}
```