← Home
For problem statement at 0-999/0-99/30-39/37/problemC.txt this is a correct solution, but verifier at 0-999/0-99/30-39/37/verifierC.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
	"strings"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}
	L := make([]int, n)
	maxL := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &L[i])
		if L[i] > maxL {
			maxL = L[i]
		}
	}

	c := make([]int, maxL+2)
	indices := make([][]int, maxL+2)
	for i := 0; i < n; i++ {
		l := L[i]
		if l <= 0 {
			fmt.Fprintln(out, "NO")
			return
		}
		c[l]++
		indices[l] = append(indices[l], i)
	}

	// Check Kraft inequality: sum c[l] / 2^l <= 1
	sum := big.NewInt(0)
	for l := 1; l <= maxL; l++ {
		if c[l] == 0 {
			continue
		}
		pow := new(big.Int).Lsh(big.NewInt(1), uint(maxL-l)) // 2^(maxL - l)
		term := new(big.Int).Mul(pow, big.NewInt(int64(c[l])))
		sum.Add(sum, term)
	}
	capacity := new(big.Int).Lsh(big.NewInt(1), uint(maxL)) // 2^maxL
	if sum.Cmp(capacity) == 1 {
		fmt.Fprintln(out, "NO")
		return
	}

	// Compute canonical first codes for each length
	first := make([]*big.Int, maxL+2)
	code := big.NewInt(0)
	for l := 1; l <= maxL; l++ {
		code.Add(code, big.NewInt(int64(c[l-1])))
		code.Lsh(code, 1)
		first[l] = new(big.Int).Set(code)
	}

	ans := make([]string, n)
	for l := 1; l <= maxL; l++ {
		if len(indices[l]) == 0 {
			continue
		}
		cur := new(big.Int).Set(first[l])
		for _, idx := range indices[l] {
			s := cur.Text(2)
			if len(s) > l {
				fmt.Fprintln(out, "NO")
				return
			}
			if len(s) < l {
				s = strings.Repeat("0", l-len(s)) + s
			}
			ans[idx] = s
			cur.Add(cur, big.NewInt(1))
		}
	}

	fmt.Fprintln(out, "YES")
	for i := 0; i < n; i++ {
		fmt.Fprintln(out, ans[i])
	}
}