AT_agc028_e.[AGC028E] High Elements

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $ (1,\ 2,\ ...\ N) $ 的排列 $ P $。

长度为 $ N $、仅由 0 和 1 组成的字符串 $ S $ 是否为好字符串，按照如下方式判定：

构造数列 $ X $ 和 $ Y $，方法如下：
- 首先，将 $ X $ 和 $ Y $ 设为空数列。
- 对于每个 $ i=1,\ 2,\ ...,\ N $，依次判断：若 $ S_i= $ 0，则将 $ P_i $ 加入 $ X $ 的末尾；若 $ S_i= $ 1，则将 $ P_i $ 加入 $ Y $ 的末尾。
若 $ X $ 中的高项个数与 $ Y $ 中的高项个数相等，则 $ S $ 是好字符串。这里，某个数列的第 $ i $ 项是高项，当且仅当该项是该数列第 $ 1 $ 项到第 $ i $ 项中的最大值。

请判断是否存在好字符串，若存在请输出字典序最小的一个。

输入格式

输入从标准输入读入，格式如下：

$ N $ $ P_1 $ $ P_2 $ $ ... $ $ P_N $

输出格式

若不存在好字符串，则输出 -1。若存在，则输出字典序最小的好字符串。

输入输出样例

输入#1
```
6
3 1 4 6 2 5
```
输出#1
```
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

说明/提示

限制

$ 1\leq N\leq 2\times 10^5 $
$ 1\leq P_i\leq N $
$ P_1,\ P_2,\ ...,\ P_N $ 互不相同。
输入均为整数。

样例解释 1

若取 $ S= $ 001001，则 $ X=(3,\ 1,\ 6,\ 2) $，$ Y=(4,\ 5) $。$ X $ 中的高项为第 $ 1 $ 项和第 $ 3 $ 项。$ Y $ 中的高项为第 $ 1 $ 项和第 $ 2 $ 项。高项个数相等，因此 001001 是好字符串。不存在字典序更小的好字符串，所以答案为 001001。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页