← 返回题目列表

Codeforces · 1227/G

G. 不一样

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

给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$,其中 $$$a_i$$$ 表示第 $$$i$$$ 位置处的块数。保证$$$1 \le a_i \le n$$$。

在一个操作中,您可以选择给定数组的索引子集,并删除每个索引中的一个块。您无法从没有方块的位置移除方块。

您选择的所有子集都应该不同(唯一)。

您需要使用最多 $$$n+1$$$ 操作来删除数组中的所有块。可以证明答案总是存在的。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^3$$$) — 给定数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 位置 $$$1, 2, \dots, n$$$ 处的块数。

输出

在第一行打印一个整数 $$$op$$$ ($$$0 \le op \le n+1$$$)。

在下面的每一行 $$$op$$$ 中,打印长度为 $$$n$$$ 的二进制字符串 $$$s$$$。如果$$$s_i=$$$'0',则意味着位置$$$i$$$不在所选子集中。否则,$$$s_i$$$ 应等于“1”,并且位置$$$i$$$ 位于所选子集中。

所有二进制字符串应该是不同的(唯一的),并且 $$$a_i$$$ 应等于所有选定的二进制字符串中 $$$s_i$$$ 的总和。

如果有多个可能的答案,您可以打印任何一个。

可以证明答案总是存在的。

示例

输入 #1

5
5 5 5 5 5

输出 #1

6
11111
01111
10111
11011
11101
11110

输入 #2

5
5 1 1 1 1

输出 #2

5
11000
10000
10100
10010
10001

输入 #3

5
4 1 5 3 4

输出 #3

5
11111
10111
10101
00111
10100

注意

在第一个示例中,块的数量像这样减少:

$$$\lbrace 5,5,5,5,5 \rbrace \to \lbrace 4,4,4,4,4 \rbrace \to \lbrace 4,3,3,3,3 \rbrace \to \lbrace 3,3,2,2,2 \rbrace \to \lbrace 2,2,2,1,1 \rbrace \to \lbrace 1,1,1,1,0 \rbrace \ 到 \lbrace 0,0,0,0,0 \rbrace$$$。我们可以注意到,每个操作都与其他操作不同。