B - 01 Graph Construction 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900 点

問題文

0,1 のみからなる文字列の組 (S,T) が次の条件をすべて満たすとき (そしてそのときのみ) それを良い文字列組と呼ぶことにします．

  • S,T に含まれる 0 の個数は等しい．
  • S,T に含まれる 1 の個数は等しい．

特に，良い文字列組 (S,T) について，S,T の長さは同じです．

良い文字列組 (S,T) に対し，無向グラフ G(S,T) を次のように定義します．

  • S の長さを L とする．頂点 1,2,\cdots,L からなるグラフ g をつくる．
  • S に含まれる 0 の個数を n とする． S に含まれる 0 の index を 1 \leq a_1 < a_2 < \cdots < a_n \leq L とする． T に含まれる 0 の index を 1 \leq b_1 < b_2 < \cdots < b_n \leq L とする． 各 1 \leq i \leq n に対し，頂点 a_i と頂点 b_i を結ぶ辺を g に追加する．
  • S に含まれる 1 の個数を m とする． S に含まれる 1 の index を 1 \leq c_1 < c_2 < \cdots < c_m \leq L とする． T に含まれる 1 の index を 1 \leq d_1 < d_2 < \cdots < d_m \leq L とする． 各 1 \leq i \leq m に対し，頂点 c_i と頂点 d_i を結ぶ辺を g に追加する．
  • 以上の手順で得た g を G(S,T) とする．

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． 以下の条件をすべて満たす良い文字列組 (S,T) を 1 つ見つけてください．

  • S の長さを L とする．N \leq L \leq 10^5 である．
  • 各 1 \leq i,j \leq N について，G(S,T) で頂点 i と頂点 j が同じ連結成分に属すとき，そしてそのときのみ 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) を求めると，次のようになります．

  • 4 頂点ならなるグラフ g を用意する．
  • S に含まれる 0 の index は (1,2) で，T に含まれる 0 の index は (3,4) である． 辺 (1,3),(2,4) を g に追加する．
  • S に含まれる 1 の index は (3,4) で，T に含まれる 1 の index は (1,2) である． 辺 (3,1),(4,2) を 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

Score : 900 points

Problem Statement

A pair of strings (S, T) consisting of 0 and 1 is called good if and only if all of the following conditions are satisfied.

  • S and T contain the same number of 0s.
  • S and T contain the same number of 1s.

Particularly, for a good string pair (S, T), S and T have the same length.

For a good string pair (S, T), we define an undirected graph G(S, T) as follows.

  • Let L be the length of S. Create a graph g with vertices 1, 2, \cdots, L.
  • Let n be the number of 0s in S. Let the indices of 0s in S be 1 \leq a_1 < a_2 < \cdots < a_n \leq L. Let the indices of 0s in T be 1 \leq b_1 < b_2 < \cdots < b_n \leq L. For each 1 \leq i \leq n, add an edge between vertices a_i and b_i to g.
  • Let m be the number of 1s in S. Let the indices of 1s in S be 1 \leq c_1 < c_2 < \cdots < c_m \leq L. Let the indices of 1s in T be 1 \leq d_1 < d_2 < \cdots < d_m \leq L. For each 1 \leq i \leq m, add an edge between vertices c_i and d_i to g.
  • The graph g obtained through the above steps is G(S, T).

You are given an integer sequence A = (A_1, A_2, \cdots, A_N) of length N. Find one good string pair (S, T) satisfying all of the following conditions.

  • Let L be the length of S. It satisfies N \leq L \leq 10^5.
  • For each pair 1 \leq i, j \leq N, vertices i and j belong to the same connected component in G(S, T) if and only if A_i = A_j.

It can be proved that a solution always exists under the constraints of this problem.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print a solution in the following format:

L
S
T

Here, L is the length of S and T. If multiple solutions exist, any of them will be accepted.

Sample Input 1

3
1 2 1

Sample Output 1

4
0011
1100

For the S and T in the sample output, we obtain G(S, T) as follows:

  • Prepare a graph g with 4 vertices.
  • The indices of 0s in S are (1, 2), and the indices of 0s in T are (3, 4). Add edges (1, 3) and (2, 4) to g.
  • The indices of 1s in S are (3, 4), and the indices of 1s in T are (1, 2). Add edges (3, 1) and (4, 2) to g.
  • Let G(S, T) = g.

G(S, T) has a connected component with vertices (1, 3) and another with vertices (2, 4). This satisfies all the conditions, so this (S, T) is a valid output.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

5
01010
01010

Sample Input 3

6
1 1 1 1 1 1

Sample Output 3

6
011111
111110

Sample Input 4

10
1 2 3 2 4 3 4 4 5 6

Sample Output 4

21
000101010111100011011
011010000010101111110