問題一覧 > 通常問題

No.3338 Whole Reverse Contradiction

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 6
作問者 : 👑 kencho / テスター : cn_449 👑 みうね
お気に入りにしたユーザー ProblemId : 12749 / 自分の提出
問題文最終更新日: 2025-11-08 02:00:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 487 (順位表) の他の問題:

Problem Statement

There is a grid with $N$ rows and $N$ columns. Let $(i,\ j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.
Each cell contains an integer; the written integers are between $1$ and $N^2$, inclusive, and are all distinct.

There are the following $2$ types of operations.

  • Operation $1$: Choose $1$ row and reverse that row left to right.
  • Operation $2$: Choose $1$ column and reverse that column upside down.
You may perform these operations between $0$ and $4N^2$ times in total, inclusive.
However, as in operation $1$ $\rightarrow$ operation $2$ $\rightarrow$ operation $1$ $\rightarrow$ operation $2$ $\rightarrow$ $\cdots$, throughout the entire sequence of operations, you must perform operation $1$ at odd-numbered steps and operation $2$ at even-numbered steps.

Given that the number initially written in cell $(i,\ j)$ is $A_{i,j}$, is it possible to make the number written in cell $(i,\ j)$ equal to $(i - 1) \times N + j$ after the operations are completed?
If it is possible, find one example of such a sequence of operations; if it is impossible, report so.

You are given $T$ test cases; solve each of them.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 10^4$
  • $2 \leq N \leq 300$
  • $1 \leq A_{i,j} \leq N^2$
  • $A_{i_1, j_1} \neq A_{i_2, j_2}\ ((i_1,\ j_1) \neq (i_2,\ j_2))$
  • The sum of $N^2$ in $1$ input file does not exceed $9 \times 10^4$.

Input

The input is given from Standard Input in the following format, where $case_i$ denotes the $i$-th case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$N$
$A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, N}$
$A_{2, 1}\ A_{2, 2}\ \cdots\ A_{2, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \cdots\ A_{N, N}$

Output

For each case, if no sequence of operations satisfying the conditions exists, output -1; if one exists, output one example of it in the following format.

$K$
$B_1\ B_2\ \cdots\ B_K$

Here, $K$ is the total number of operations. When $i$ is odd, $B_i$ represents which row from the top is chosen in the $i$-th operation, and when $i$ is even, $B_i$ represents which column from the left is chosen in the $i$-th operation.
Print a newline at the end of the output for each case.

Sample

Sample 1
Input
2
4
1 2 15 4
8 11 6 5
9 10 7 12
13 14 3 16
2
1 2
3 4
Output
2
2 3
0

For the $1$st test case, if you reverse the $2$nd row from the top and the $3$rd column from the left in this order, the numbers written in the grid change as shown in the figure below, and the number written in the cell in the $i$-th row from the top and the $j$-th column from the left becomes $(i - 1) \times N + j$, so this is a correct answer.

For the $2$nd test case, the condition is satisfied from the start, so no operations need to be performed.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。