CF314A.Sereja and Contest
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
During the last Sereja's Codesecrof round the server crashed many times, so the round was decided to be made unrated for some participants.
Let's assume that n people took part in the contest. Let's assume that the participant who got the first place has rating _a_1, the second place participant has rating _a_2, ..., the n-th place participant has rating a__n. Then changing the rating on the Codesecrof site is calculated by the formula
.
After the round was over, the Codesecrof management published the participants' results table. They decided that if for a participant d__i < k, then the round can be considered unrated for him. But imagine the management's surprise when they found out that the participants' rating table is dynamic. In other words, when some participant is removed from the rating, he is removed from the results' table and the rating is recalculated according to the new table. And of course, all applications for exclusion from the rating are considered in view of the current table.
We know that among all the applications for exclusion from the rating the first application to consider is from the participant with the best rank (the rank with the minimum number), for who d__i < k. We also know that the applications for exclusion from rating were submitted by all participants.
Now Sereja wonders, what is the number of participants to be excluded from the contest rating, and the numbers of the participants in the original table in the order of their exclusion from the rating. Pay attention to the analysis of the first test case for a better understanding of the statement.
在上一场 Sereja 的 Codesecrof 比赛中,服务器多次崩溃,因此该场比赛对部分参赛者被定为“不计分”(unrated)。
假设共有 $ n $ 人参加了比赛。设获得第 1 名的参赛者评分为 $ a_1 $,第 2 名的参赛者评分为 $ a_2 $,……,第 $ n $ 名的参赛者评分为 $ a_n $。则 Codesecrof 网站上每位参赛者的评分变化量由如下公式计算:

比赛结束后,Codesecrof 管理方公布了参赛者的成绩表。他们规定:若某位参赛者的评分变化量 $ d_i < k $,则该场比赛对其可视为“不计分”。但管理方惊讶地发现,该评分表是动态更新的——即当某位参赛者被从评分系统中移除后,他也会从成绩表中被删除,且其余所有人的评分变化量将依据更新后的成绩表重新计算。当然,所有“申请移出评分”的请求,均基于当前时刻的成绩表进行处理。
我们已知:在所有提交的“移出评分”申请中,优先处理排名最高(即名次编号最小)且满足 $ d_i < k $ 的那位参赛者的申请。同时,我们也知道:所有参赛者均提交了移出评分的申请。
现在 Sereja 想知道:最终有多少名参赛者将被从本次比赛的评分中移除?以及,在原始成绩表中,这些被移除者的编号(按其被移除的先后顺序)依次是什么?请特别注意第一个样例的分析,以更深入理解题意。
输入格式
The first line contains two integers n, k (1 ≤ n ≤ 2·105, - 109 ≤ k ≤ 0). The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — ratings of the participants in the initial table.
第一行包含两个整数 n、k(1≤n≤2⋅105,−109≤k≤0)。第二行包含 n 个以空格分隔的整数 a1,a2,…,an(1≤ai≤109)——初始排行榜中各参赛者的评分。
输出格式
Print the numbers of participants in the order in which they were removed from the table. Print the initial numbers of the participants, that is, the numbers that the participants had in the initial table.
按参与者从圆桌中被移除的顺序输出其人数。输出参与者的初始编号,即他们在初始圆桌中的编号。
输入输出样例
输入#1
5 0 5 3 4 1 2
输出#1
2 3 4
输入#2
10 -10 5 5 1 7 5 1 2 4 9 2
输出#2
2 4 5 7 8 9
说明/提示
Consider the first test sample.
- Initially the sequence of the contest participants' ratings equals [5, 3, 4, 1, 2]. You can use this sequence to calculate the sequence of rating changes: [0, -9, -13, 8, 14]. According to the problem statement, the application of the participant who won the second place will be considered first.
- As soon as the second place winner is out from the ratings, the participants' rating sequence will equal [5, 4, 1, 2]. By this sequence you can count the new sequence of rating changes: [0, -8, 2, 6]. According to the problem statement, the application of the participant who won the second place will be considered. Initially this participant won third place.
- The new rating sequence equals [5, 1, 2], the new sequence of rating changes equals [0, -1, 1]. The second place participant's application is taken into consideration, initially this participant won the fourth place.
- The new rating sequence equals [5, 2], the new sequence of rating changes equals [0, 0]. No more applications will be considered.
Thus, you should print 2, 3, 4.
考虑第一个测试样例。
- 最初,竞赛参赛者的评分数列为 [5, 3, 4, 1, 2]。利用该数列可计算出评分数列的变化量为 [0, -9, -13, 8, 14]。根据题目描述,首先考虑获得第二名的参赛者的申请。
- 一旦第二名的参赛者从评分数列中移除,剩余参赛者的评分数列变为 [5, 4, 1, 2]。由此数列可计算出新的评分数列变化量:[0, -8, 2, 6]。根据题目描述,接下来考虑获得第二名的参赛者的申请。最初,该参赛者获得第三名。
- 新的评分数列为 [5, 1, 2],新的评分数列变化量为 [0, -1, 1]。此时考虑第二名参赛者的申请,该参赛者最初获得第四名。
- 新的评分数列为 [5, 2],新的评分数列变化量为 [0, 0]。此后不再考虑任何申请。
因此,应输出 2, 3, 4。
输入解题思路,AI测评打分。不知道怎么写?