← 返回题目列表

AtCoder · arc181_c

C. 行和列顺序

中文机器翻译题面 查看原题

分数: 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。

  1. |X| \lt |Y| 和 X_1X_2\ldots X_{|X|} = Y_1Y_2\ldots Y_{|X|}.
  2. 存在一个整数 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