問題一覧 > 通常問題

No.3726 Flawless Flow

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 55
作問者 : 👑 kencho / テスター : 👑 p-adic uruzunyaa
お気に入りにしたユーザー ProblemId : 13570 / 自分の提出
問題文最終更新日: 2026-11-02 04:26:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
グリッド構築24題 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。