No.3602 Queen XOR Score
タグ : / 解いたユーザー数 15
作問者 : 👑
gomaazarasi
ぽえ
問題文
縦 $H$ マス，横 $W$ マスのマス目があります．上から $i(1 \leq i \leq H)$ 番目，左から $j(1 \leq j \leq W)$ 番目のマスを，マス $(i, j)$ と表記します．
各マスには整数が書かれています．マス $(i, j)$ に書かれている整数は $A_{i, j}$ です．
このマス目上で，クイーンのコマを動かします．クイーンのコマは，マス目の範囲内のマスに自由に出入り可能ですが，範囲外のマスには出入りできません．
これから，$Q$ 個のクエリが与えられるので，それぞれについて答えてください．$i$ 番目のクエリの内容は次の通りです．
あなたは，これから以下に示す手続きを行います．
- まず，マス目の範囲内の好きなマスを $1$ つ選び，コマを置く．
- 次に，以下を $0$ 回以上 $2HW - 1$ 回以下の回数繰り返す．
- 今クイーンのコマが置かれているマスから $1$ 回の移動で到達できるマスを $1$ つ選び，そのマスにコマを移動させる．
この一連の手続きの中で，クイーンのコマを移動させた回数を $K$ としたとき，クイーンのコマが置かれたマスに書かれている整数を順に $B_0, B_1, \dots, B_K$ とします（最初にクイーンを置いたマスも含まれることに注意してください．また，同じマスにクイーンのコマが累計複数回置かれたことがあった場合でもそれらは別々に扱います）．
整数 $X_i$ が与えられます．$B_0 \oplus B_1 \oplus \dots \oplus B_K = X_i$ となるような手続きの方法が存在するかどうか判定し，存在する場合は具体例を $1$ つ構成してください．
クイーンのコマの移動方法について（クリックで開く）
クイーンのコマは，$1$ 回の移動において，縦・横・斜めの方向に，通る経路のマスが全て出入り可能である限り自由なマス数進むことができます．ただし，今いるマスにとどまることを $1$ 回の移動とみなすことはできません．厳密には，マス $(i, j)$ にあるクイーンのコマは次のような移動が可能です．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j + k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j + l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j - k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j - l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j + k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j + l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j - k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j - l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j + k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j + l)$ はクイーンのコマが出入り可能なマスである．
- 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j - k)$ への移動が可能である．
- $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j - l)$ はクイーンのコマが出入り可能なマスである．
制約
- 入力は全て整数
- $2 \leq H \leq 20$
- $2 \leq W \leq 20$
- $0 \leq A_{i, j} < 2^{60}$
- $1 \leq Q \leq 500$
- $0 \leq X_i < 2^{60}$
入力
入力は以下の形式で標準入力から与えられる．
$H$ $W$
$A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$
$Q$
$X_1$
$X_2$
$\vdots$
$X_Q$
出力
$Q$ 個のクエリについて順番に，次のように出力せよ．
$i$ 番目のクエリにおいて，条件を満たす手続きの方法が存在しなければ -1 を出力せよ．存在する場合は，クイーンのコマを移動させた回数（最初に好きなマスに置くことは移動の回数には含まれない）を $K$，最初に置いたマスを $(x_0, y_0)$，$j$ 回目の移動先のマスを $(x_j, y_j)$ として，以下の形式で出力せよ．ここで，$0 \leq K \leq 2HW - 1$ を満たす必要がある．
条件を満たす手続きの方法が複数ある場合は，そのうちのどれを出力しても正解となる．
$K$ $x_0$ $y_0$ $x_1$ $y_1$ $\vdots$ $x_K$ $y_K$
各クエリの末尾には必ず改行せよ．
サンプル
サンプル1
入力
2 2 6 2 3 0 3 1 6 10
出力
2 1 2 2 2 2 1 0 1 1 -1
$1$ 番目のクエリでは，クイーンのコマは $(1, 2) \rightarrow (2, 2) \rightarrow (2, 1)$ と移動します．
このとき，$2 \oplus 0 \oplus 3 = 1$ となるため，確かに条件を満たしています．
$2$ 番目のクエリでは，クイーンのコマは マス $(1, 1)$ に置かれてから移動をしません．このように，移動の回数が $0$ 回でもよいことに注意してください．
$3$ 番目のクエリでは，条件を満たす手続きの方法は存在しません．
サンプル2
入力
3 3 1 1 1 1 1 1 1 1 1 1 0
出力
5 1 1 1 2 1 3 3 1 3 2 3 3
移動回数を最小化する必要はありません．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。