分数: 900 点
问题陈述
一对字符串 (S, T) 组成 0 和 1 被称为 好 当且仅当满足以下所有条件时。
- S 和 T 包含相同数量的
0s。 - S 和 T 包含相同数量的
1s。
特别是对于一对好的琴弦 (S, T), S 和 T 具有相同的长度。
对于一个好的字符串对 (S, T),我们定义一个无向图 G(S, T) 如下。
- 让 L 的长度 S。创建图表 g 带有顶点 1, 2, \cdots, L.
- 让 n 是数量
0s 在 S。令指数为0s 在 S be 1 \leq a_1 < a_2 < \cdots < a_n \leq L。令指数为0s 在 T be 1 \leq b_1 < b_2 < \cdots < b_n \leq L。对于每个 1 \leq i \leq n,在顶点之间添加一条边 a_i 和 b_i to g. - 让 m 是数量
1s 在 S。令指数为1s 在 S be 1 \leq c_1 < c_2 < \cdots < c_m \leq L。令指数为1s 在 T be 1 \leq d_1 < d_2 < \cdots < d_m \leq L。对于每个 1 \leq i \leq m,在顶点之间添加一条边 c_i 和 d_i to g. - 图表 通过上述步骤得到的 g 为 G(S, T).
给你一个整数序列 A = (A_1, A_2, \cdots, A_N) 长度 N。 找到一对好的弦 (S, T) 满足以下所有条件。
- 让 L 的长度 S。它满足 N \leq L \leq 10^5.
- 对于每对 1 \leq i, j \leq N,顶点 i 和 j 属于相同的连接组件 G(S, T) 当且仅当 A_i = A_j.
可以证明,在该问题的约束下,总存在解。
约束
- 1 \leq N \leq 100
- 1 \leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
按以下格式打印解决方案:
L S T
在这里, L 是长度 S 和 T。 如果存在多个解决方案,则其中任何一个都将被接受。
示例输入 1
3 1 2 1
示例输出 1
4 0011 1100
对于 S 和 T 在示例输出中,我们获得 G(S, T) 如下:
- 准备图表 g 与 4 顶点。
- 的指数
0s 在 S 是 (1, 2),以及索引0s 在 T 是 (3, 4)。添加边缘 (1, 3) 和 (2, 4) to g. - 的指数
1s 在 S 是 (3, 4),以及索引1s 在 T 是 (1, 2)。添加边缘 (3, 1) 和 (4, 2) to g. - 让 G(S, T) = g.
G(S, T) 有一个带有顶点的连接组件 (1, 3) 和另一个带有顶点的 (2, 4)。 这满足了所有条件,所以这 (S, T) 是有效输出。
示例输入 2
5 1 2 3 4 5
示例输出 2
5 01010 01010
示例输入 3
6 1 1 1 1 1 1
示例输出 3
6 011111 111110
示例输入 4
10 1 2 3 2 4 3 4 4 5 6
示例输出 4
21 000101010111100011011 011010000010101111110