← Home
For problem statement at 1000-1999/1500-1599/1540-1549/1545/problemC.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1540-1549/1545/verifierC.go ends with test 1 failed
input:
1
9
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8
7 2 3 4 5 6 1 8 9
9 3 4 5 6 7 8 2 1
3 4 5 6 7 8 2 1 9
1 5 6 7 8 9 4 2 3
5 4 7 8 9 1 2 3 6
6 7 8 9 1 2 3 5 4
4 8 9 1 2 3 7 5 6
8 9 3 2 1 4 5 6 7
9 2 1 3 4 5 6 7 8
expected:2
2 3 5 6 8 9 10 13 16
actual:2
1 2 3 4 5 6 7 8 9

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	var readInt = func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	tCases := 0
	for _, b := range scanner.Bytes() {
		tCases = tCases*10 + int(b-'0')
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for t := 0; t < tCases; t++ {
		n := readInt()
		A := make([][]int, 2*n)
		for i := 0; i < 2*n; i++ {
			A[i] = make([]int, n)
			for j := 0; j < n; j++ {
				A[i][j] = readInt()
			}
		}

		adjCv := make([][][]int, n)
		for i := 0; i < n; i++ {
			adjCv[i] = make([][]int, n)
		}
		for i := 0; i < 2*n; i++ {
			for c := 0; c < n; c++ {
				v := A[i][c] - 1
				adjCv[c][v] = append(adjCv[c][v], i)
			}
		}

		activeArrays := make([]bool, 2*n)
		for i := 0; i < 2*n; i++ {
			activeArrays[i] = true
		}

		activeCount := make([][]int, n)
		coveredCv := make([][]bool, n)
		for i := 0; i < n; i++ {
			activeCount[i] = make([]int, n)
			coveredCv[i] = make([]bool, n)
			for j := 0; j < n; j++ {
				activeCount[i][j] = len(adjCv[i][j])
			}
		}

		queue := make([]int, 0)
		inQueue := make([]bool, 2*n)

		for c := 0; c < n; c++ {
			for v := 0; v < n; v++ {
				if activeCount[c][v] == 1 {
					u := adjCv[c][v][0]
					if !inQueue[u] {
						queue = append(queue, u)
						inQueue[u] = true
					}
				}
			}
		}

		chosen := make([]bool, 2*n)
		eliminated := make([]bool, 2*n)

		var deactivate func(x int, isChosen bool)
		deactivate = func(x int, isChosen bool) {
			if !activeArrays[x] {
				return
			}
			activeArrays[x] = false

			if isChosen {
				chosen[x] = true
				for c := 0; c < n; c++ {
					v := A[x][c] - 1
					coveredCv[c][v] = true
				}
			} else {
				eliminated[x] = true
			}

			for c := 0; c < n; c++ {
				v := A[x][c] - 1
				activeCount[c][v]--

				if activeCount[c][v] == 1 && !coveredCv[c][v] {
					lastActive := -1
					for _, y := range adjCv[c][v] {
						if activeArrays[y] {
							lastActive = y
							break
						}
					}
					if lastActive != -1 && !inQueue[lastActive] {
						queue = append(queue, lastActive)
						inQueue[lastActive] = true
					}
				}
			}
		}

		head := 0
		for head < len(queue) {
			u := queue[head]
			head++

			if !activeArrays[u] {
				continue
			}

			deactivate(u, true)

			for c := 0; c < n; c++ {
				v := A[u][c] - 1
				for _, w := range adjCv[c][v] {
					if activeArrays[w] {
						deactivate(w, false)
					}
				}
			}
		}

		remaining := make([]int, 0)
		for i := 0; i < 2*n; i++ {
			if activeArrays[i] {
				remaining = append(remaining, i)
			}
		}

		adjRem := make([][]int, 2*n)
		for c := 0; c < n; c++ {
			for v := 0; v < n; v++ {
				if !coveredCv[c][v] && activeCount[c][v] == 2 {
					x, y := -1, -1
					for _, arr := range adjCv[c][v] {
						if activeArrays[arr] {
							if x == -1 {
								x = arr
							} else {
								y = arr
							}
						}
					}
					if x != -1 && y != -1 {
						adjRem[x] = append(adjRem[x], y)
						adjRem[y] = append(adjRem[y], x)
					}
				}
			}
		}

		visited := make([]bool, 2*n)
		components := 0
		color := make([]int, 2*n)
		for i := 0; i < 2*n; i++ {
			color[i] = -1
		}

		for _, i := range remaining {
			if !visited[i] {
				components++
				q := make([]int, 0)
				q = append(q, i)
				visited[i] = true
				color[i] = 0
				chosen[i] = true

				for len(q) > 0 {
					curr := q[0]
					q = q[1:]
					for _, neighbor := range adjRem[curr] {
						if !visited[neighbor] {
							visited[neighbor] = true
							color[neighbor] = 1 - color[curr]
							if color[neighbor] == 0 {
								chosen[neighbor] = true
							}
							q = append(q, neighbor)
						}
					}
				}
			}
		}

		ans := 1
		for i := 0; i < components; i++ {
			ans = (ans * 2) % 998244353
		}

		fmt.Fprintln(out, ans)
		first := true
		for i := 0; i < 2*n; i++ {
			if chosen[i] {
				if !first {
					fmt.Fprint(out, " ")
				}
				fmt.Fprint(out, i+1)
				first = false
			}
		}
		fmt.Fprintln(out)
	}
}