No.3739 Stronger Network
Problem Statement
You will write a non-negative integer in each cell of an $H \times W$ toroidal grid.
Among the ways of writing that satisfy all of the following conditions, find one that minimizes the maximum of the written non-negative integers.
- The non-negative integers written in the cells are all distinct.
- For any $2$ adjacent cells, letting $x, y$ be the pair of non-negative integers written in them, there exists a non-negative integer $k$ such that $x \oplus y = 2^k$.
- $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.
Here, let $(i, j)$ denote the cell in the $i+1$-th row from the top and the $j+1$-th column from the left of the grid. The cells adjacent to $(i, j)$ are the at most $4$ cells $((i-1) \bmod H, j)$, $((i+1) \bmod H, j)$, $(i, (j-1) \bmod W)$, $(i, (j+1) \bmod W)$.
If there are multiple answers, you may output any of them. If no such way of writing exists, output -1.
Constraints
- All inputs are integers.
- $2 \leq H, W$
- $HW \leq 5 \times 10^5$
Input
The input is given from Standard Input in the following format.
$H\ W$
Output
If a way of writing that satisfies the conditions exists, output one example that minimizes the maximum of the written non-negative integers, in the following format. Here, $A_{i, j}$ is the integer written in the cell in the $i+1$-th row from the top and the $j+1$-th column from the left of the grid. If no way of writing that satisfies the conditions exists, output -1.
$A_{0, 0}\ A_{0, 1}\ \ldots\ A_{0, W-1}$
$A_{1, 0}\ A_{1, 1}\ \ldots\ A_{1, W-1}$
$\vdots$
$A_{H-1, 0}\ A_{H-1, 1}\ \ldots\ A_{H-1, W-1}$
Print a newline at the end.
Visualizer
A web-based visualizer for the output is available here.
During the contest, sharing visualization results and discussing solutions or insights are prohibited. Please be careful.
Also, as a rule, questions about the visualizer's specifications are not accepted. Please use it only as an auxiliary tool.
Sample
Sample 1
Input
2 4
Output
0 4 5 1 2 6 7 3
The non-negative integers from $0$ to $7$ could be written. The maximum is $7$, and this is the minimum possible.
For example, the following output is also accepted.
5 1 0 4 7 3 2 6
Sample 2
Input
3 2
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。