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)
}
}