問題一覧 > 通常問題

No.3736 Purely Bool Hell

レベル : / AI推定難易度 : 2525 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 13
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13636 / 自分の提出
問題文最終更新日: 2026-11-02 04:28:22
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 will write a non-negative integer in each cell of an $N \times N$ grid. Let $A_{i, j}$ be the integer written in the cell at the $i$-th row from the top and the $j$-th column from the left. Output one example of a way of writing that satisfies all of the following conditions. If no such way of writing exists, output -1.

  • $A_{i, j}\ (1 \le i, j \le N)$ is a non-negative integer less than $2^{30}$
  • For $i = 1, 2, \ldots, N$, $\displaystyle \bigwedge_{j=1}^{N} A_{i,j} = X_i$
  • For $j = 1, 2, \ldots, N$, $\displaystyle \bigvee_{i=1}^{N} A_{i,j} = Y_j$
  • For $k = 1, 2, \ldots, 2N-1$, $\displaystyle \bigoplus_{i+j-1=k} A_{i,j} = Z_k$

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

Definitions of the symbols
  • $\displaystyle \bigwedge_{j=1}^{N} A_{i,j}$ denotes the bitwise-AND of $A_{i,1}, A_{i,2}, \ldots, A_{i,N}$, that is, $\displaystyle A_{i,1} \mathbin{\mathrm{AND}} A_{i,2} \mathbin{\mathrm{AND}} \cdots \mathbin{\mathrm{AND}} A_{i,N}$.
  • $\displaystyle \bigvee_{i=1}^{N} A_{i,j}$ denotes the bitwise-OR of $A_{1,j}, A_{2,j}, \ldots, A_{N,j}$, that is, $\displaystyle A_{1,j} \mathbin{\mathrm{OR}} A_{2,j} \mathbin{\mathrm{OR}} \cdots \mathbin{\mathrm{OR}} A_{N,j}$.
  • Let $(i_1,j_1), (i_2,j_2), \ldots, (i_m,j_m)$ be the pairs of indices satisfying $1 \le i,j \le N$ and $i+j-1=k$. Then,
    $\displaystyle \bigoplus_{i+j-1=k} A_{i,j}$ denotes the bitwise-XOR of $A_{i_1,j_1}, A_{i_2,j_2}, \ldots, A_{i_m, j_m}$, that is, $\displaystyle A_{i_1,j_1} \mathbin{\mathrm{XOR}} A_{i_2,j_2} \mathbin{\mathrm{XOR}} \cdots \mathbin{\mathrm{XOR}} A_{i_m,j_m}$.

Constraints

  • All input values are integers
  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 500$
  • $0 \leq X_i \lt 2^{30}$
  • $0 \leq Y_j \lt 2^{30}$
  • $0 \leq Z_k \lt 2^{30}$
  • The sum of $N^2$ in $1$ input file does not exceed $2.5 \times 10^5$

Input

The input is given from standard input in the following format. Here, $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$
$X_1$ $X_2$ $\ldots$ $X_N$
$Y_1$ $Y_2$ $\ldots$ $Y_N$
$Z_1$ $Z_2$ $\ldots$ $Z_{2N-1}$

Output

For each case, if a way of writing that satisfies the conditions exists, output one example of it in the following format. If no way of writing satisfies the conditions, output -1.

$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}$

Output 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 mentioning solutions or analysis are prohibited. Please be careful.

In addition, as a rule, questions about the specifications of the visualizer are not accepted. Please use it only as an auxiliary tool.

Sample

Sample 1
Input
2
3
1 0 2
7 7 3
3 4 0 0 2
1
1
0
0
Output
3 5 1
1 6 2
7 2 2
-1
About test case $1$

The output is correct because the following hold.

  • $\displaystyle \bigwedge_{j=1}^{N} A_{1,j} = 3\ \mathrm{AND}\ 5\ \mathrm{AND}\ 1 = 1$
  • $\displaystyle \bigwedge_{j=1}^{N} A_{2,j} = 1\ \mathrm{AND}\ 6\ \mathrm{AND}\ 2 = 0$
  • $\displaystyle \bigwedge_{j=1}^{N} A_{3,j} = 7\ \mathrm{AND}\ 2\ \mathrm{AND}\ 2 = 2$
  • $\displaystyle \bigvee_{i=1}^{N} A_{i,1} = 3\ \mathrm{OR}\ 1\ \mathrm{OR}\ 7 = 7$
  • $\displaystyle \bigvee_{i=1}^{N} A_{i,2} = 5\ \mathrm{OR}\ 6\ \mathrm{OR}\ 2 = 7$
  • $\displaystyle \bigvee_{i=1}^{N} A_{i,3} = 1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 2 = 3$
  • $\displaystyle \bigoplus_{i+j-1=1} A_{i,j} = 3$
  • $\displaystyle \bigoplus_{i+j-1=2} A_{i,j} = 5\ \mathrm{XOR}\ 1 = 4$
  • $\displaystyle \bigoplus_{i+j-1=3} A_{i,j} = 1\ \mathrm{XOR}\ 6\ \mathrm{XOR}\ 7 = 0$
  • $\displaystyle \bigoplus_{i+j-1=4} A_{i,j} = 2\ \mathrm{XOR}\ 2 = 0$
  • $\displaystyle \bigoplus_{i+j-1=5} A_{i,j} = 2$
About test case $2$

No $A_{1, 1}$ satisfies all of the conditions.

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