No.3726 Flawless Flow
Problem Statement
There is a grid of size $(N+1) \times N$. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$.
You are also given permutations $A = (A_1, A_2, \ldots, A_N)$ and $B = (B_1, B_2, \ldots, B_N)$ of $(1, 2, \ldots, N)$.
Currently, the contents of permutation $A$ are written in the $1$-st row from the top of the grid, and the contents of permutation $B$ are written in the $N+1$-th row.
That is, for $i = 1, 2, \ldots, N$, cell $(1, i)$ contains $A_i$ and cell $(N+1, i)$ contains $B_i$. Nothing is written in the other cells.
Is it possible to write an integer between $1$ and $N$, inclusive, in every empty cell so that, for each $i = 1, 2, \ldots, N$, the entire set of cells containing $i$ is connected under 8-neighborhood adjacency ($8$-connected)?
Here, "the entire set of cells containing $k$ is $8$-connected" means that for any pair of cells containing $k$, one can reach one from the other by repeatedly moving to a cell containing $k$ that is adjacent vertically, horizontally, or diagonally.
If it is possible, find one way of writing the integers; if it is impossible, output -1.
Constraints
- All input values are integers.
- $2 \leq N \leq 500$
- $A$ is a permutation of $1, 2, \ldots, N$.
- $B$ is a permutation of $1, 2, \ldots, N$.
Input
The input is given from Standard Input in the following format:
$N$ $A_1\ A_2\ \ldots\ A_N$ $B_1\ B_2\ \ldots\ B_N$
Output
If there exists a way of writing that satisfies the condition, output one such way in the following format, where $C_{i, j}$ is the integer written in the cell in the $i$-th row from the top and the $j$-th column from the left of the grid. If no such way exists, output -1.
$C_{1, 1}\ C_{1, 2}\ \ldots\ C_{1, N}$
$C_{2, 1}\ C_{2, 2}\ \ldots\ C_{2, N}$
$\vdots$
$C_{N+1, 1}\ C_{N+1, 2}\ \ldots\ C_{N+1, N}$
Note that $C_{1, i} = A_i, C_{N+1, i} = B_i$ must hold for $i = 1, 2, \ldots, N$.
Output a newline at the end.
Visualizer
A web-based visualizer for the output is available here.
During the contest, sharing visualization results or mentioning solutions or observations is prohibited. Please be careful.
In principle, we do not accept questions about the specifications of the visualizer. Please use it only as an auxiliary tool.
Sample
Sample 1
Input
4 2 1 3 4 3 2 4 1
Output
2 1 3 4 2 3 1 4 3 2 1 4 2 3 4 1 3 2 4 1
The grid represented by the sample output is shown in the figure below.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。