排序比赛

题目内容

题目描述

s-quark去参加一个排序比赛,比赛的规则是:每人写一个排序程序,将一列无序的数字按从小到大排好序。当两个人对决时,可以互相出测试数据,每个人都要使用对方出的数据运行程序,耗时短者胜利。

现在,s-quark拿到了对方的程序,发现对方写的是使用随机化交换写法的快速排序,并且,对方的随机函数rand()并没有使用时间作为种子,也就是说,该rand()函数产生的伪随机数是可以被预测的。

s-quark希望该程序在运行时,每次都是以l到r范围内的最大元素为作为划分基准,这样就可以使快速排序达到最大比较次数。s-quark很快设计出了这样的序列,从而轻松赢得了比赛。而你的任务是,对于给定的数字数量n(n <= 100000),和伪随机数序列,找出一个1到n的排列,使得给定的快速排序程序每次都是以l到r范围内的最大元素作为基准进行划分。如果有多个排列满足要求,输出字典序更小的排列。

输入描述

输入的第一行为一个正整数,为题目描述中的n。

接下来一行包含n个正整数,为题目描述中的伪随机数序列。该序列当用到超过n次随机数时,会从序列的第1个整数重新开始。

输出描述

输出一行,包含n个正整数,为题目所求的1到n的排列。

样例输入

5 12 23 45 112 4123

样例输出

2 1 5 4 3

提示

提交评测
请登录后再操作

题目描述

排序比赛
1206
0
Level4
28
22
79%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在