CF38G Queue

在一个寒冷的冬夜，我们的主角 Vasya 正在排队购买前往 Codeforces 决赛的火车票。像往常一样，售票员说他要离开 5 分钟，结果却离开了一个小时。为了打发无聊的时间，Vasya 开始分析排队的机制，而他的发现让他大吃一惊。 每个人都由两个数字描述：$a_{i}$，表示他当前任务的重要性（数字越大，任务越重要）；$c_{i}$，表示他良心的体现。所有的 $a_{i}$ 组成了一个 $1$ 到 $n$ 的排列。 当前队列中有 $n-1$ 个人。我们来看看第 $n$ 个到来的人是如何行动的。首先，他站在队伍的末尾，然后进行以下操作：如果他前面那个人的任务重要性 $a_{i}$ 小于他自己的 $a_{n}$，那么他们就交换位置（就像这样：第 $n$ 个人对他前面的人说：“呃……不好意思，可是我的确很重要，能让我靠前一点吗？”），接下来他又向他前面的人提出同样的请求，如此反复。但是如果 $a_{i}$ 大于 $a_{n}$，那么前进过程就停止。然而，第 $n$ 个人最多只能执行 $c_{n}$ 次这样的操作。 本题设定为当第 $n$ 个人进入队列时，前面 $n-1$ 人之间的交换过程已经全部结束。如果可以交换，则一定会交换。 你的任务是帮助 Vasya 模拟上述过程，找出所有交换结束后队列中的排队顺序。

第一行输入一个整数 $n$，表示总共有 $n$ 个人加入队列（$1 \leq n \leq 10^{5}$）。接下来 $n$ 行依次给出每个人的信息，每行包含两个用空格分隔的整数 $a_{i}$ 和 $c_{i}$（$1 \leq a_{i} \leq n$，$0 \leq c_{i} \leq n$）。所有 $a_{i}$ 互不相同。

输出由 $1$ 到 $n$ 组成的一个排列，表示最终排队顺序，从队头到队尾。排列中的第 $i$ 个数字表示最终站在第 $i$ 个位置上的那个人的编号。编号按照输入顺序，从 $1$ 开始。数字之间用空格分隔。

由 ChatGPT 5 翻译