No.3338 Whole Reverse Contradiction
タグ : / 解いたユーザー数 5
作問者 :
kencho
/ テスター :
cn_449
みうね
問題文
縦 $N$ 行、横 $N$ 列のマス目があり、上から $i$ 行目、左から $j$ 列目のマスを $(i,\ j)$ と表すことにします。
各マスには整数が書かれており、書かれている整数は $1$ 以上 $N^2$ 以下かつ全て異なります。
さて、以下の $2$ 種類の操作があります。
- 操作 $1$ : 行を $1$ つ選び、その行を左右反転する。
- 操作 $2$ : 列を $1$ つ選び、その列を上下反転する。
ただし、操作 $1$ $\rightarrow$ 操作 $2$ $\rightarrow$ 操作 $1$ $\rightarrow$ 操作 $2$ $\rightarrow$ $\cdots$ のように、操作列全体を通して奇数回目には操作 $1$ 、偶数回目には操作 $2$ を行う必要があります。
最初にマス $(i,\ j)$ に書かれている数字が $A_{i,j}$ であるとき、操作が完了した後のマス $(i,\ j)$ に書かれている数字が $(i - 1) \times N + j$ となるようにすることは可能ですか？
可能な場合はそのような操作列の一例を求め、不可能な場合はその旨を報告してください。
$T$ 個のテストケースが与えられるため、それぞれに解答してください。
制約
- 入力は全て整数
- $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))$
- $1$ 個の入力ファイルにおける $N^2$ の総和は $9 \times 10^4$ を超えない
入力
入力は以下の形式で標準入力から与えられる。ここで、$case_i$ は $i$ 番目のケースを意味する。
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
各テストケースは以下の形式で与えられる。
$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}$
出力
各ケースに対し、条件を満たす操作列が存在しない場合は -1 を、存在する場合は以下の形式でその一例を出力してください。
$K$ $B_1\ B_2\ \cdots\ B_K$
ただし、$K$ は操作の合計回数であり、$i$ が奇数のとき、$B_i$ は $i$ 回目の操作で選ぶ行が上から何行目であるかを表し、$i$ が偶数のとき、$B_i$ は $i$ 回目の操作で選ぶ列が左から何列目であるかをを表します。
各ケースに対する出力の最後に改行してください。
サンプル
サンプル1
入力
2 4 1 2 15 4 8 11 6 5 9 10 7 12 13 14 3 16 2 1 2 3 4
出力
2 2 3 0
$1$ つ目のテストケースについては、上から $2$ 行目、左から $3$ 列目をこの順に反転すると、マス目に書かれた数字は下図の様に変化し、上から $i$ 行目、左から $j$ 番目のマスに書かれた数字が $(i - 1) \times N + j$ となるため、これは正答となります。
$2$ つ目のテストケースについては、最初から条件を満たしているため、操作を行う必要はありません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。