分数: 600 点
问题陈述
给你两种排列 P=(P_1,P_2,\dots,P_N) 和 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N).
写入字符之一 0 和 1 在每个单元格中 N-by-N 网格,以便满足以下所有条件:
- 让 S_i 是通过连接中的字符获得的字符串 i从第 1-st 到 N第列。然后, S_{P_1} < S_{P_2} < \dots < S_{P_N} 按字典顺序排列。
- 让 T_i 是通过连接中的字符获得的字符串 i第 列 1-st 到 N- 第行。然后, T_{Q_1} < T_{Q_2} < \dots < T_{Q_N} 按字典顺序排列。
可以证明对于任意 P 和 Q,至少有一种方法可以写出满足所有条件的字符。
什么是“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 使得以下两项均成立:
- 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
输出
按照以下格式打印满足条件的网格的填充方式,其中 A_{ij} 是写入的字符 i第行和 j第列:
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