#P4319. cerc2008 Suffix reconstruction
cerc2008 Suffix reconstruction
[CERC 2008] Suffix reconstruction
题目描述
对一个长度为 的字符串 ,将从每个位置开始的后缀按字典序从小到大排列。设第 个后缀的起始位置是 ,则 是 的后缀数组。若一个字符串是另一个的真前缀,较短的字符串字典序在前。
例如,abbaabab 的后缀数组为 。
给定这组起始位置,判断是否存在一个仅由小写英文字母组成的字符串,恰好有这个后缀数组。若存在,输出任意一个这样的字符串。
输入格式
第一行一个整数 ,表示字符串长度。第二行 个整数 ,是 至 的一个排列。第 项是字典序第 小的后缀的起始位置,位置从 开始编号。
输出格式
若有解,输出一行一个合法字符串。若无解,输出一行 -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
数据规模与约定
。本地版每份输入为一组,原赛题面把多组放在同一份输入中。