← 返回题目列表

AtCoder · agc068_b

B. 01 图形构建

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

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