E. 姜姜的密码

    传统题 1000ms 256MiB

姜姜的密码

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem: 姜姜的密码

时间限制:1s

空间限制:256MB

Description

​ 高中的时候,原力清理大师上课不敢公然和姜姜讲话,只好请姜姜制定一套密码,偷偷摸摸传递信息。令原力清理大师头疼的是,姜姜制定的密码实在是太过复杂了,以至于完全看不懂。愚蠢的原力清理大师只好先从数字部分开始向姜姜请教,至于其他的字母之类的,下辈子再说吧 QAQQAQ

​ 这里特别研究有关 11nn 的排列。对于一个 11nn 的排列,姜姜将其映射为其在这个数列中的逆序数。通俗的说,对于任意 1in1 \leq i \leq n ,若其映射前值为 aia_i ,其映射后的值即为所有满足 ai<aj(1ji1)a_i < a_j (1 \leq j \leq i-1)aja_j 的数量。

​ 原力清理大师的数学头脑这辈子就这样了。由于姜姜要突击检查原力清理大师,所以他希望你能帮帮他破解一下姜姜的密码(感谢你为世界和平做出的贡献)。

Input Format

​ 输入共两行。

​ 第一行一个正整数 nn ,代表所给数列的长度。

​ 第二行共 nn 个非负整数,为所给出的逆序数数列。

Output Format

​ 若该数列可以被还原,输出共一行 nn 个数字,为还原后的一个 nn 的排列;否则输出 1-1

Data Range

  • 1n2e51 \leq n \leq 2e5
  • 任意 1in1 \leq i \leq n ,有 0ain0 \leq a_i \leq n

Input Example #1:

3
0 1 2

Output Example #1:

3 2 1

Explanation

最后一个数字最小,中间的次之,前面的最大,包是 3213 2 1 的。

可以证明存在原数列的逆序数数列可以对应唯一的原数列。

2024秋悬赏令第四周

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-11-3 18:00
结束于
2024-11-10 18:00
持续时间
168 小时
主持人
参赛人数
62