B - Split and Reverse Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1100 点

問題文

0,1 からなる長さ N の整数列 X=(X_1,X_2,\cdots,X_N) が与えられます．

あなたは以下の操作を 0 回以上行うことができます．

  • X の各要素を A または B のグループに分類する． そして各グループに対して，そこに含まれる要素の順番を反転させる． より厳密に言えば，グループに含まれる要素が X_{i_1},X_{i_2},\cdots,X_{i_s} (i_1<i_2<\cdots<i_s) であるとき，X_{i_j} の値を X_{i_{s+1-j}} で置き換えるという操作をすべての 1 \leq j \leq s に対して同時に行う．

あなたの目標は X を広義単調増加にすることです． 目標を達成するために必要な最小の操作回数と，その操作方法を求めてください． なお，この問題の制約下で常に解が存在することが証明できます．

1 つの入力につき，T ケースを解いてください．

制約

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 0 \leq X_i \leq 1
  • T ケースにわたる N の総和は 250000 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N
X_1 X_2 \cdots X_N

出力

各ケースについて，以下の形式で出力せよ．

k
s_1
s_2
\vdots
s_k

ただしここで k は必要な最小の操作回数であり，s_i は i 回目の操作を表す文字列である． s_i は A,B からなる長さ N の文字列であり，s_i の j 文字目は，i 回目の操作で X_j を入れるグループを表す． 解が複数ある場合はどれを出力してもよい．

入力例 1

2
4
0 1 0 1
5
0 0 1 1 1

出力例 1

2
AABA
BBBB
0

1 つ目のテストケースは，以下のように 2 回の操作で目標を達成することができ，これが最小の操作回数です．

  • 1 回目の操作: s_1=AABA で操作する．(X_1,X_2,X_4) がグループ A に含まれるため，これらの順番を反転させ，(X_1,X_2,X_4)=(1,1,0) となる． 同様に，(X_3) がグループ B に含まれるため，これらの順番を反転させ，(X_3)=(0) となる． よって，全体では X=(1,1,0,0) となる．

  • 2 回目の操作: s_2=BBBB で操作する．() がグループ A に含まれるため，これらの順番を反転させ，()=() となる． 同様に，(X_1,X_2,X_3,X_4) がグループ B に含まれるため，これらの順番を反転させ，(X_1,X_2,X_3,X_4)=(0,0,1,1) となる． よって，全体では X=(0,0,1,1) となる．

2 つ目のテストケースでは，操作を 0 回行うことで目標を達成できます．

Score : 1100 points

Problem Statement

You are given an integer sequence X=(X_1,X_2,\cdots,X_N) of length N consisting of 0 and 1.

You can perform the following operation zero or more times:

  • Classify each element of X into group A or group B. Then, for each group, reverse the order of the elements it contains. More formally, if the elements contained in a group are X_{i_1},X_{i_2},\cdots,X_{i_s} (i_1<i_2<\cdots<i_s), then for all 1 \leq j \leq s, simultaneously replace the value of X_{i_j} with X_{i_{s+1-j}}.

Your goal is to make X non-decreasing. Find the minimum number of operations needed to achieve the goal and the way to perform the operations. It can be proved that a solution always exists under the constraints of this problem.

Solve T cases for one input.

Constraints

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 0 \leq X_i \leq 1
  • The sum of N over the T cases is at most 250000.
  • All input values are integers.

Input

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

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
X_1 X_2 \cdots X_N

Output

For each case, output in the following format:

k
s_1
s_2
\vdots
s_k

Here, k is the minimum number of operations needed, and s_i is a string representing the i-th operation. s_i is a string of length N consisting of A and B, and the j-th character of s_i represents the group to which X_j is assigned in the i-th operation. If there are multiple solutions, you may output any of them.

Sample Input 1

2
4
0 1 0 1
5
0 0 1 1 1

Sample Output 1

2
AABA
BBBB
0

For the first test case, the goal can be achieved in two operations as follows, which is the minimum number of operations:

  • First operation: Use s_1=AABA. Since (X_1,X_2,X_4) are in group A, reverse their order, resulting in (X_1,X_2,X_4)=(1,1,0). Similarly, since (X_3) is in group B, reverse their order, resulting in (X_3)=(0). Thus, overall we get X=(1,1,0,0).

  • Second operation: Use s_2=BBBB. Since () are in group A, reverse their order, resulting in ()=(). Similarly, since (X_1,X_2,X_3,X_4) are in group B, reverse their order, resulting in (X_1,X_2,X_3,X_4)=(0,0,1,1). Thus, overall we get X=(0,0,1,1).

For the second test case, the goal can be achieved by performing the operation zero times.