問題一覧 > 通常問題

No.3724 Domination

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 53
作問者 : 👑 kencho / テスター : 👑 p-adic uruzunyaa
お気に入りにしたユーザー ProblemId : 13567 / 自分の提出
問題文最終更新日: 2026-11-02 04:26:07
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

You are given sequences $R = (R_1, R_2, \ldots, R_N)$ and $C = (C_1, C_2, \ldots, C_N)$ of length $N$. $R$ is a permutation of $1, 2, \ldots, N$.

You will write an integer between $1$ and $N$, inclusive, in each cell of an $N \times N$ grid. Find one way of writing the integers that satisfies all of the following conditions. If no such way exists, output -1.

  • For $1 \leq i \leq N$, the mode of the $N$ integers written in row $i$ is only $R_i$
  • For $1 \leq i \leq N$, the mode of the $N$ integers written in column $i$ is only $C_i$

You are given $T$ test cases; output the answer for each of them.

Constraints

  • All input values are integers
  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 1000$
  • $R$ is a permutation of $1, 2, \ldots, N$
  • $1 \leq C_i \leq N$
  • The sum of $N^2$ in $1$ input file does not exceed $10^6$

Partial Score

This problem has partial scoring based on subtasks.

SubtaskScoreConstraints
部分点20% (50 pts)$C$ は $1, 2, \cdots , N$ の順列
満点80% (200 pts)追加の制約は無い

Input

The input is given from standard input in the following format, where $case_i$ denotes the $i$-th case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$N$
$R_1\ R_2\ \ldots\ R_N$
$C_1\ C_2\ \ldots\ C_N$

Output

For each case, output -1 if no way of writing the integers satisfies the conditions; otherwise, output one such way in the following format. Here, $A_{i, j}$ denotes the integer written in the cell at the $i$-th row from the top and the $j$-th column from the left of the grid.

$A_{1, 1}\ A_{1, 2}\ \ldots\ A_{1, N}$
$A_{2, 1}\ A_{2, 2}\ \ldots\ A_{2, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \ldots\ A_{N, N}$

Print a newline at the end of the output for each case.

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.

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
2
4
2 3 1 4
3 2 4 1
2
1 2
2 1
Output
2 2 1 3
3 3 3 1
1 2 4 1
3 4 4 1
-1

Note that in each row and each column, the given value must be the unique mode.

The grid represented by the sample output for the $1$-st test case, along with the mode of each row and each column, is shown in the figure below.

This test case is included in the subtask cases.

Sample 2
Input
1
3
2 1 3
3 3 1
Output
2 3 2
3 1 1
3 3 1

This test case is not included in the subtask cases.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。