AT_arc181_c.[ARC181C] Row and Column Order

给定 $ (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 $ 如何，至少存在一种满足所有条件的填法。

字典序 $ X < Y $ 的定义如下：对于字符串 $ X=X_1X_2\dots X_{|X|} $ 和 $ Y=Y_1Y_2\dots Y_{|Y|} $，**$ X < Y $ 按字典序成立**，当且仅当满足以下两条之一。这里 $ |X|,\ |Y| $ 分别表示 $ X,\ Y $ 的长度。

1. $ |X| < |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 $。

输入通过标准输入给出，格式如下：

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

如果存在多种满足条件的填法，输出任意一种均可。

数据范围

• $ 2 \leq N \leq 500 $
• $ P,Q $ 是 $ (1,2,\dots,N) $ 的排列
• 输入均为整数

样例解释 1

对于本样例，$ 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 $，满足条件。

由 ChatGPT 4.1 翻译