No.3602 Queen XOR Score
タグ : / 解いたユーザー数 12
作問者 : 👑
gomaazarasi
ぽえ
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell in the $i(1 \leq i \leq H)$-th row from the top and the $j(1 \leq j \leq W)$-th column from the left is denoted by cell $(i, j)$.
An integer is written on each cell. The integer written on cell $(i, j)$ is $A_{i, j}$.
A queen piece moves on this grid. The queen piece can freely enter and leave cells within the grid, but cannot enter or leave cells outside the grid.
You are given $Q$ queries, so answer each of them. The $i$-th query is as follows.
You will perform the procedure described below.
- First, choose any $1$ cell within the grid and place the piece on it.
- Then, repeat the following at least $0$ times and at most $2HW - 1$ times.
- Choose $1$ cell that can be reached in $1$ move from the cell where the queen piece is currently placed, and move the piece to that cell.
Let $K$ be the number of times the queen piece was moved during this procedure, and let $B_0, B_1, \dots, B_K$ be the integers written on the cells where the queen piece was placed, in order (note that the cell where the queen was initially placed is included. Also, if the queen piece was placed on the same cell multiple times in total, those are treated separately).
An integer $X_i$ is given. Determine whether there exists a procedure such that $B_0 \oplus B_1 \oplus \dots \oplus B_K = X_i$, and if one exists, construct $1$ specific example.
About how the queen piece moves (click to open)
In $1$ move, the queen piece can advance any number of cells in the vertical, horizontal, or diagonal direction, as long as all the cells on its path can be entered and left. However, staying on the current cell cannot be counted as $1$ move. Strictly speaking, a queen piece on cell $(i, j)$ can move as follows.
- For a positive integer $k$, it can move to cell $(i, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i, j - l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j - l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j - l)$ is a cell that the queen piece can enter and leave.
Constraints
- All inputs are integers
- $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}$
Input
The input is given from standard input in the following format.
$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$
Output
For the $Q$ queries, in order, output as follows.
For the $i$-th query, if no procedure satisfying the condition exists, output -1. If one exists, let $K$ be the number of times the queen piece is moved (the initial placement on a cell of your choice is not counted as a move), let $(x_0, y_0)$ be the initially chosen cell, and let $(x_j, y_j)$ be the destination cell of the $j$-th move, and output in the following format. Here, $0 \leq K \leq 2HW - 1$ must be satisfied.
If there are multiple procedures satisfying the condition, any of them will be accepted.
$K$ $x_0$ $y_0$ $x_1$ $y_1$ $\vdots$ $x_K$ $y_K$
Be sure to output a newline at the end of each query.
Sample
Sample 1
Input
2 2 6 2 3 0 3 1 6 10
Output
2 1 2 2 2 2 1 0 1 1 -1
In the $1$-st query, the queen piece moves as $(1, 2) \rightarrow (2, 2) \rightarrow (2, 1)$.
Here, $2 \oplus 0 \oplus 3 = 1$, so the condition is indeed satisfied.
In the $2$-nd query, the queen piece does not move after being placed on cell $(1, 1)$. Note that the number of moves may be $0$ like this.
In the $3$-rd query, no procedure satisfying the condition exists.
Sample 2
Input
3 3 1 1 1 1 1 1 1 1 1 1 0
Output
5 1 1 1 2 1 3 3 1 3 2 3 3
You do not need to minimize the number of moves.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。