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

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

样例 1

输入

3
1 2 3
2 1 3

输出

001
101
110

样例 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

输出

010001111110101
001000000101001
010001001100010
010000011110010
010011101101101
100101110100000
111100011001000
000001001100000
100011011000101
000111101011110
101010101010101
011010101011110
010011000010011
100110010110101
000101101100100

说明/提示

数据范围

• $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 翻译