Not Same
Contest: Technocup 2020 - Elimination Round 3
Difficulty rating: 2600
Tags: constructive algorithms

You are given an integer array $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ represents the number of blocks at the $$$i$$$-th position. It is guaranteed that $$$1 \le a_i \le n$$$.

In one operation you can choose a subset of indices of the given array and remove one block in each of these indices. You can't remove a block from a position without blocks.

All subsets that you choose should be different (unique).

You need to remove all blocks in the array using at most $$$n+1$$$ operations. It can be proved that the answer always exists.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — length of the given array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — numbers of blocks at positions $$$1, 2, \dots, n$$$.

Output format:
In the first line print an integer $$$op$$$ ($$$0 \le op \le n+1$$$).

In each of the following $$$op$$$ lines, print a binary string $$$s$$$ of length $$$n$$$. If $$$s_i=$$$'0', it means that the position $$$i$$$ is not in the chosen subset. Otherwise, $$$s_i$$$ should be equal to '1' and the position $$$i$$$ is in the chosen subset.

All binary strings should be distinct (unique) and $$$a_i$$$ should be equal to the sum of $$$s_i$$$ among all chosen binary strings.

If there are multiple possible answers, you can print any.

It can be proved that an answer always exists.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the number of blocks decrease like that:

$$$\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 \to \lbrace 0,0,0,0,0 \rbrace$$$. And we can note that each operation differs from others.

Example input:
5
5 5 5 5 5

Example output:
6
11111
01111
10111
11011
11101
11110

Example input:
5
5 1 1 1 1

Example output:
5
11000
10000
10100
10010
10001

Editorial:
The solution can be inspired by the output format :)
First of all, sort all numbers in decreasing order. Let them be $$$A_{1}, A_{2} \dots , A_{n}$$$. We will construct the answer column by column. Let us use a set of binary string to represent a series of operations. For example $$$\lbrace 10,10,10,11 \rbrace$$$ represent operations for $$$\lbrace 4,1\rbrace $$$(invalid, however).
Then we compress the same operations in a operation set as the number of this operation occurs. For example, $$$\lbrace 10,10,10,11 \rbrace$$$ can be compressed as $$$\lbrace 3,1 \rbrace$$$ as there's three $$$10$$$ and one $$$11$$$. Note we do not care whether the operation is, we only care how many times it occurs.
Now, as we construct the answer column by column, new numbers will be added. A new number can split some elements in the compress set. For example, we add a new $$$1$$$ in $$$\lbrace 4,1 \rbrace$$$ as it becomes $$$\lbrace 4,1,1 \rbrace$$$. We can turn the operation set $$$\lbrace 10,10,10,11 \rbrace$$$ into $$$\lbrace 100,100,101,11 \rbrace$$$, while the compress set turns $$$\lbrace 2,1,1 \rbrace$$$ from $$$\lbrace 3,1 \rbrace$$$. In general, we can turn $$$\lbrace X \rbrace$$$ into $$$\lbrace Y , X - Y \rbrace$$$ uses a number $$$X(1 \leq Y < X)$$$. Special condition: $$$\lbrace Y \rbrace$$$ can keep same but use number $$$Y$$$.
Special judge for $$$A_{1} = 1$$$, thus we use one operation to erase all numbers.
Obviously the first compress set is $$$\lbrace A_{1} \rbrace$$$, represent operation set $$$\lbrace 1,1,1,1, \dots ,1 \rbrace$$$.
If $$$A_{1} = A_{2}$$$, turn the second compress set as $$$\lbrace 1,A_{1} - 1,1 \rbrace$$$, otherwise turn it as $$$\lbrace A_{2} , A_{1} - A_{2} \rbrace$$$.
Then we maintain the compress set by keeping the sum of the elements same but the number of the elements strictly increasing. For a current compress set, let $$$X$$$ be the minimal element, and $$$Y$$$ be the new number added. If $$$Y < X$$$, split $$$X$$$ into $$$\lbrace Y , X - Y \rbrace$$$. Otherwise split $$$X$$$ into $$$\lbrace 1 , X - 1 \rbrace$$$, the left number $$$(Y-X+1)$$$ can be randomly placed.
The left number can be randomly placed if and if only the sum of the elements is larger then $$$Y$$$. Obviously the sum of the elements equals to $$$A_{1}$$$ or $$$A_{1} + 1$$$. If the sum of the elements equals to $$$A_{1}$$$, then $$$Y \leq A_{2} < A_{1}$$$.
After all split operations, the compress set must be $$$\lbrace 1,1,1 \dots ,1 \rbrace$$$, which means all operation differ from each other. We can construct the final answer now in $$$O(n^2)$$$ .