21969번 - Cheerleader 서브태스크점수다국어

In preparation for the Fo(1)otball cup, the cheerleaders from Little Square’s school are trying to create a new routine. There are 2^N cheerleaders with distinct heights between 0 and 2^N − 1. The cheerleaders stand in a row. The height of the cheerleader that is initially at position i is h[i] for 1 ≤ i ≤ 2^N.

The cheerleaders know two coordinate dance moves:

• The big swap. In this move, the first 2^N−1 cheerleaders swap places with the last 2^N−1 cheerleaders.
• The big split. In this move, the cheerleaders at odd positions go to the beginning of the row, and the cheerleaders at even positions go to the end of the row.

For instance, a big swap on 8 elements has the following effect:

And a big split on 8 elements has the following effect:

Now, define the number of inversions of a row of cheerleaders with heights h'[1], . . . , h'[2^N] as the number of pairs (i, j), 1 ≤ i < j ≤ 2^N where h'[i] > h'[j]. The cheerleaders want to know a sequence of dance moves that minimises the number of inversions in the resulting row.

On the first line of the input you will find N. On the second line of the input you will find 2^N integers, that represent h[1], . . . , h[2^N].

On the first line of the output, print the minimum number of inversions that can be achieved. On the second line of the output, write a string that represents a sequence of dance moves that leads to that minimum number of inversions. In this string, a 1 represents a big swap, and a 2 represents a big split. Any sequence of moves that leads to the minimum number of inversions will be accepted.

• 0 ≤ N ≤ 17.
• N can be 0.
• If you output the correct minimum number of inversions, but the string of moves is incorrect, you will receive X points. The value of X varies from subtask to subtask.

• N ≤ 4
• X = 8

• N ≤ 7
• X = 5

• N ≤ 11
• X = 20

• N ≤ 16
• It is guaranteed that the minimum number of inversions that can be achieved is 0.
• X = 0

• No additional restrictions.
• X = 21