#P4319. cerc2008 Suffix reconstruction

    ID: 3535 传统题 1000ms 128MiB 尝试: 262 已通过: 149 难度: 6 上传者: 标签>难度分类普及+/提高-字符串后缀数组构造与建模序列构造贪心贪心保持领先CF1900鸣谢Claris提供SPJ

cerc2008 Suffix reconstruction

[CERC 2008] Suffix reconstruction

题目描述

对一个长度为 nn 的字符串 ss,将从每个位置开始的后缀按字典序从小到大排列。设第 jj 个后缀的起始位置是 pjp_j,则 p1,p2,…,pnp_1,p_2,\ldots,p_n 是 ss 的后缀数组。若一个字符串是另一个的真前缀,较短的字符串字典序在前。

例如,abbaabab 的后缀数组为 (4,7,5,1,8,3,6,2)(4,7,5,1,8,3,6,2)。

给定这组起始位置,判断是否存在一个仅由小写英文字母组成的字符串,恰好有这个后缀数组。若存在,输出任意一个这样的字符串。

输入格式

第一行一个整数 nn,表示字符串长度。第二行 nn 个整数 p1,…,pnp_1,\ldots,p_n,是 11 至 nn 的一个排列。第 jj 项是字典序第 jj 小的后缀的起始位置,位置从 11 开始编号。

输出格式

若有解,输出一行一个合法字符串。若无解,输出一行 -1。

样例 #1

样例输入 #1

4
2 3 4 1

样例输出 #1

dabc

样例 #2

样例输入 #2

2
1 2

样例输出 #2

ab

样例 #3

样例输入 #3

2
2 1

样例输出 #3

aa

样例 #4

样例输入 #4

3
2 3 1

样例输出 #4

bab

样例 #5

样例输入 #5

6
3 4 5 1 2 6

样例输出 #5

suffix

样例 #6

样例输入 #6

14
3 10 2 12 14 5 13 4 1 8 6 11 7 9

样例输出 #6

reconstruction

样例 #7

样例输入 #7

7
5 1 7 4 3 2 6

样例输出 #7

issofun

数据规模与约定

1≤n≤5000001\le n\le500000。本地版每份输入为一组,原赛题面把多组放在同一份输入中。

CERC 2008 原题