← Home
For problem statement at 1000-1999/1700-1799/1760-1769/1765/problemA.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1760-1769/1765/verifierA.go ends with failed to build reference: exit status 1
# command-line-arguments
./1765A.go:193:1: syntax error: unexpected EOF, expected }

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) skip() {
	for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
}

func (fs *FastScanner) NextInt() int {
	fs.skip()
	sign := 1
	if fs.idx < fs.n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return sign * val
}

func (fs *FastScanner) NextBytes() []byte {
	fs.skip()
	start := fs.idx
	for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
		fs.idx++
	}
	return fs.data[start:fs.idx]
}

func writeInts(w *bufio.Writer, a []int) {
	for i, v := range a {
		if i > 0 {
			w.WriteByte(' ')
		}
		w.WriteString(strconv.Itoa(v))
	}
	w.WriteByte('\n')
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()
	m := fs.NextInt()

	rows := make([][]byte, n)
	bcnt := (n + 63) >> 6
	cols := make([][]uint64, m)
	for j := 0; j < m; j++ {
		cols[j] = make([]uint64, bcnt)
	}

	for i := 0; i < n; i++ {
		s := fs.NextBytes()
		rows[i] = s
		word := i >> 6
		bit := uint(i & 63)
		mask := uint64(1) << bit
		for j := 0; j < m; j++ {
			if s[j] == '1' {
				cols[j][word] |= mask
			}
		}
	}

	adj := make([][]int, m)
	for u := 0; u < m; u++ {
		for v := 0; v < m; v++ {
			if u == v {
				continue
			}
			subset := true
			eq := true
			for k := 0; k < bcnt; k++ {
				if cols[u][k]&^cols[v][k] != 0 {
					subset = false
					break
				}
				if cols[u][k] != cols[v][k] {
					eq = false
				}
			}
			if subset && (!eq || u < v) {
				adj[u] = append(adj[u], v)
			}
		}
	}

	pairU := make([]int, m)
	pairV := make([]int, m)
	dist := make([]int, m)
	for i := 0; i < m; i++ {
		pairU[i] = -1
		pairV[i] = -1
	}

	bfs := func() bool {
		q := make([]int, 0, m)
		for u := 0; u < m; u++ {
			if pairU[u] == -1 {
				dist[u] = 0
				q = append(q, u)
			} else {
				dist[u] = -1
			}
		}
		found := false
		for head := 0; head < len(q); head++ {
			u := q[head]
			for _, v := range adj[u] {
				pu := pairV[v]
				if pu == -1 {
					found = true
				} else if dist[pu] == -1 {
					dist[pu] = dist[u] + 1
					q = append(q, pu)
				}
			}
		}
		return found
	}

	var dfs func(int) bool
	dfs = func(u int) bool {
		for _, v := range adj[u] {
			pu := pairV[v]
			if pu == -1 || (dist[pu] == dist[u]+1 && dfs(pu)) {
				pairU[u] = v
				pairV[v] = u
				return true
			}
		}
		dist[u] = -1
		return false
	}

	for bfs() {
		for u := 0; u < m; u++ {
			if pairU[u] == -1 {
				dfs(u)
			}
		}
	}

	starts := make([]int, 0)
	for v := 0; v < m; v++ {
		if pairV[v] == -1 {
			starts = append(starts, v)
		}
	}

	paths := make([][]int, 0, len(starts))
	vis := make([]bool, m)
	for _, s := range starts {
		cur := s
		path := make([]int, 0)
		for cur != -1 && !vis[cur] {
			vis[cur] = true
			path = append(path, cur)
			cur = pairU[cur]
		}
		paths = append(paths, path)
	}
	for v := 0; v < m; v++ {
		if !vis[v] {
			cur := v
			path := make([]int, 0)
			for cur != -1 && !vis[cur] {
				vis[cur] = true
				path = append(path, cur)
				cur = pairU[cur]
			}
			paths = append(paths, path)
		}
	}

	equalCols := func(a, b int) bool {
		for i := 0; i < bcnt; i++ {
			if cols[a][i] != cols[b][i] {
				return false
			}
		}
		return true
	}

	k := len(paths)
	group := make([]int, m)
	thr := make([]int, m)
	dev := make([][]int, n)
	for i := 0; i < n; i++ {
		dev[i] = make([]int, k)
	}

	for g, path := range paths {
		rank := make([]int, len(path))
		distinct := 0
		for i, col := range path {
			if i == 0 || !equalCols(path[i-1], col) {
				distinct++
			}
			rank[i] = distinct
		}
		for i, col := range path {
			group[col] = g + 1
			thr[col] = distinct - rank[i] + 2
		}
		for i := 0; i < n; i++ {
			level := 1
			for _, col := range path {
				if rows[i][col] == '1' {
					level = thr[col]
					break
				}
			}
			dev[i][g] = level
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	w.WriteString(strconv.Itoa(k))
	w.WriteByte('\n')
	writeInts(w, group)
	writeInts(w, thr)
	for i := 0; i < n; i++ {
		writeInts(w, dev[i])
	}
	w.Flush()
}