(cache)E - High Elements

コンテスト時間: 2018-10-13(土) 12:00 ~ 2018-10-13(土) 14:30 (150分) AtCoderホームへ戻る

E - High Elements 解説

実行時間制限: 2 sec / メモリ制限: 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 Copy

Copy

6
3 1 4 6 2 5

出力例 1 Copy

Copy

$S =$ 001001 とすると、 $X = (3, 1, 6, 2)$ , $Y = (4, 5)$ となります。 $X$ の中で高い項は、 $1$ 項目と $3$ 項目です。また、 $Y$ の中で高い項は、 $1$ 項目と $2$ 項目です。高い項の数が等しいので、001001 はよい文字列です。これより辞書順で小さいよい文字列は存在しないので、001001 が答えになります。

入力例 2 Copy

Copy

5
1 2 3 4 5

出力例 2 Copy

Copy

-1

入力例 3 Copy

Copy

7
1 3 2 5 6 4 7

出力例 3 Copy

Copy

入力例 4 Copy

Copy

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 Copy

Copy

000000000001100101010010011101

Score : points

You are given , a permutation of .

A string of length consisting of and is a when it meets the following criterion:

The sequences and are constructed as follows:
- First, let and be empty sequences.
- For each , in this order, append to the end of if , and append it to the end of if .
If and have the same number of elements, is a good string. Here, the -th element of a sequence is called when that element is the largest among the elements from the -st to -th element in the sequence.

are all distinct.

Let . Then, and . The high elements in is the first and third elements, and the high elements in is the first and second elements. As they have the same number of high elements, is a good string. There is no good string that is lexicographically smaller than this, so the answer is .