/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N), Q=(Q_1,Q_2,\dots,Q_N) が与えられます。
N 行 N 列からなるマス目の各マスに文字 0, 1 のいずれかを書き込み、以下の条件がすべて成り立つようにしてください。
- i 行目のマスに書かれている文字を、 1,2,\dots,N 列目の順につなげて得られる文字列を S_i としたとき、辞書順で S_{P_1} < S_{P_2} < \dots < S_{P_N} が成り立つ
- i 列目のマスに書かれている文字を、 1,2,\dots,N 行目の順につなげて得られる文字列を T_i としたとき、辞書順で T_{Q_1} < T_{Q_2} < \dots < T_{Q_N} が成り立つ
なお、どのような P,Q に対しても、条件をすべて満たす書き込み方が 1 つ以上あることが証明できます。
辞書順で X < Y が成り立つとは？
文字列 X=X_1X_2\dots X_{|X|} と Y = Y_1Y_2\dots Y_{|Y|} について、辞書順で X < Y が成り立つとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|X|, |Y| はそれぞれ X, Y の長さを表します。
- |X| \lt |Y| かつ X_1X_2\ldots X_{|X|} = Y_1Y_2\ldots Y_{|X|}。
- ある整数 1 \leq i \leq \min\lbrace |X|, |Y| \rbrace が存在して、下記の 2 つがともに成り立つ。
- X_1X_2\ldots X_{i-1} = Y_1Y_2\ldots Y_{i-1}
- X_i が Y_i より小さい。
制約
- 2 \leq N \leq 500
- P,Q は (1,2,\dots,N) の順列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \dots P_N Q_1 Q_2 \dots Q_N
出力
i 行 j 列 に書き込む文字を A_{ij} として、条件を満たす書き込み方を以下の形式で出力せよ。
A_{11}A_{12}\dots A_{1N}
\vdots
A_{N1}A_{N2}\dots A_{NN}
条件を満たす書き込み方が複数存在する場合は、いずれを出力しても正解となる。
入力例 1
3 1 2 3 2 1 3
出力例 1
001 101 110
この入出力例の場合、 S_1=001 , S_2=101 , S_3=110 であり、 T_1=011 , T_2=001 , T_3=110 です。よって S_1 < S_2 < S_3 かつ T_2 < T_1 < T_3 が成り立ち、条件を満たします。
入力例 2
15 8 15 10 2 4 3 1 13 5 12 9 6 14 11 7 4 1 5 14 3 12 13 7 11 8 6 2 9 15 10
出力例 2
010001111110101 001000000101001 010001001100010 010000011110010 010011101101101 100101110100000 111100011001000 000001001100000 100011011000101 000111101011110 101010101010101 011010101011110 010011000010011 100110010110101 000101101100100
Score : 600 points
Problem Statement
You are given two permutations P=(P_1,P_2,\dots,P_N) and Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N).
Write one of the characters 0 and 1 in each cell of an N-by-N grid so that all of the following conditions are satisfied:
- Let S_i be the string obtained by concatenating the characters in the i-th row from the 1-st to the N-th column. Then, S_{P_1} < S_{P_2} < \dots < S_{P_N} in lexicographical order.
- Let T_i be the string obtained by concatenating the characters in the i-th column from the 1-st to the N-th row. Then, T_{Q_1} < T_{Q_2} < \dots < T_{Q_N} in lexicographical order.
It can be proved that for any P and Q, there is at least one way to write the characters that satisfies all the conditions.
What does "X < Y in lexicographical order" mean?
For strings X=X_1X_2\dots X_{|X|} and Y = Y_1Y_2\dots Y_{|Y|}, "X < Y in lexicographical order" means that 1. or 2. below holds. Here, |X| and |Y| denote the lengths of X and Y, respectively.
- |X| \lt |Y| and X_1X_2\ldots X_{|X|} = Y_1Y_2\ldots Y_{|X|}.
- There exists an integer 1 \leq i \leq \min\lbrace |X|, |Y| \rbrace such that both of the following are true:
- X_1X_2\ldots X_{i-1} = Y_1Y_2\ldots Y_{i-1}
- X_i is less than Y_i.
Constraints
- 2 \leq N \leq 500
- P and Q are permutations of (1,2,\dots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N Q_1 Q_2 \dots Q_N
Output
Print a way to fill the grid that satisfies the conditions in the following format, where A_{ij} is the character written at the i-th row and j-th column:
A_{11}A_{12}\dots A_{1N}
\vdots
A_{N1}A_{N2}\dots A_{NN}
If there are multiple ways to satisfy the conditions, any of them will be accepted.
Sample Input 1
3 1 2 3 2 1 3
Sample Output 1
001 101 110
In this sample, S_1=001, S_2=101, S_3=110, and T_1=011, T_2=001, T_3=110. Therefore, S_1 < S_2 < S_3 and T_2 < T_1 < T_3 hold, satisfying the conditions.
Sample Input 2
15 8 15 10 2 4 3 1 13 5 12 9 6 14 11 7 4 1 5 14 3 12 13 7 11 8 6 2 9 15 10
Sample Output 2
010001111110101 001000000101001 010001001100010 010000011110010 010011101101101 100101110100000 111100011001000 000001001100000 100011011000101 000111101011110 101010101010101 011010101011110 010011000010011 100110010110101 000101101100100