問題一覧 > 通常問題

No.1078 I love Matrix Construction

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 60
作問者 : tko919tko919 / テスター : QCFiumQCFium
2 ProblemId : 4307 / 出題時の順位表
問題文最終更新日: 2020-05-19 17:47:44

問題文

整数 $N$ と長さ $N$ の配列 $S,T,U$ が与えられます。以下の条件を満たすような $N \times N$ の行列 $a$ をどれか1つ構築してください。

  • $a_{i,j}$ は $0$ もしくは $1$
  • $1 \le i,j \le N$ なる全ての組 $(i,j)$ について、 $a_{S_i,j}+a_{j,T_i} \times 2 \neq U_i$
ただし、条件を満たす行列が存在しない場合もあるかもしれません。

入力

$N$
$S_1\ S_2\ \cdots\ S_N$
$T_1\ T_2\ \cdots\ T_N$
$U_1\ U_2\ \cdots\ U_N$

入力は全て整数
$1 \le N \le 500$
$1 \le S_i,T_i \le N$
$0 \le U_i \le 3$

出力

条件を満たす行列が存在する場合は、そのような行列 $1$ つを以下の形式で出力せよ。

$a_{1,1} \cdots\ a_{1,N}$
$\vdots$
$a_{N,1} \cdots\ a_{N,N}$
条件を満たす行列なら何を出力してもいいことに注意せよ。
条件を満たす行列が存在しない場合は-1を出力せよ。

サンプル

サンプル1
入力
3
2 1 2
3 3 1
3 1 0
出力
0 0 0
1 0 1
0 0 0

例えば $(i,j)=(1,2)$ については $a_{2,2}+a_{2,3} \times 2=2 \neq 3$ となり条件を満たしています。

サンプル2
入力
4
4 4 3 3
2 1 1 2
1 0 0 3
出力
-1

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