/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
(1,\ 2,\ ...\ N) の順列 P が与えられます。
0, 1 からなる長さ N の文字列 S がよい文字列であるかどうかは、以下の様に判定されます。
- 数列 X, Y を次のように構築する。
- まず、X, Y を空の数列とする。
- 各 i=1,\ 2,\ ...\ N について、この順に、S_i=
0なら X の末尾に、S_i=1なら Y の末尾に P_i を追加する。
- X の中にある高い項の個数と Y の中にある高い項の個数が等しいならば、S はよい文字列である。 ここで、ある数列の i 番目の項が高いとは、その項が数列の 1 番目から i 番目の項の中で最大であることを意味する。
よい文字列が存在するか判定し、存在するならその中で辞書順最小のものを求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- P_1,\ P_2,\ ...\ P_N はすべて異なる。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 ... P_N
出力
よい文字列が存在しないならば -1 と出力せよ。
存在するならば、その中で辞書順最小のものを出力せよ。
入力例 1
6 3 1 4 6 2 5
出力例 1
001001
S= 001001 とすると、X=(3,\ 1,\ 6,\ 2), Y=(4,\ 5) となります。
X の中で高い項は、1 項目と 3 項目です。
また、Y の中で高い項は、1 項目と 2 項目です。
高い項の数が等しいので、001001 はよい文字列です。
これより辞書順で小さいよい文字列は存在しないので、001001 が答えになります。
入力例 2
5 1 2 3 4 5
出力例 2
-1
入力例 3
7 1 3 2 5 6 4 7
出力例 3
0001101
入力例 4
30 1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30
出力例 4
000000000001100101010010011101
Score : 1400 points
Problem Statement
You are given P, a permutation of (1,\ 2,\ ...\ N).
A string S of length N consisting of 0 and 1 is a good string when it meets the following criterion:
- The sequences X and Y are constructed as follows:
- First, let X and Y be empty sequences.
- For each i=1,\ 2,\ ...\ N, in this order, append P_i to the end of X if S_i=
0, and append it to the end of Y if S_i=1.
- If X and Y have the same number of high elements, S is a good string. Here, the i-th element of a sequence is called high when that element is the largest among the elements from the 1-st to i-th element in the sequence.
Determine if there exists a good string. If it exists, find the lexicographically smallest such string.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- P_1,\ P_2,\ ...\ P_N are all distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 ... P_N
Output
If a good string does not exist, print -1.
If it exists, print the lexicographically smallest such string.
Sample Input 1
6 3 1 4 6 2 5
Sample Output 1
001001
Let S= 001001. Then, X=(3,\ 1,\ 6,\ 2) and Y=(4,\ 5).
The high elements in X is the first and third elements, and the high elements in Y is the first and second elements.
As they have the same number of high elements, 001001 is a good string.
There is no good string that is lexicographically smaller than this, so the answer is 001001.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
-1
Sample Input 3
7 1 3 2 5 6 4 7
Sample Output 3
0001101
Sample Input 4
30 1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30
Sample Output 4
000000000001100101010010011101