← 返回题目列表

Codeforces · 314/A

A. Sereja 和比赛

中文机器翻译题面 查看原题

在 Sereja 的 Codesecrof 上一轮比赛中,服务器多次崩溃,因此决定对某些参与者取消该轮比赛的评级。

假设有 n 人参加了比赛。假设获得第一名的参与者的评级为a1,第二名的参与者的评级为a2,...,第n名的参与者的评级为an。然后,更改 Codesecrof 网站上的评级是通过公式 $$d_i = \sum_{j=1}^{i-1}(a_j \cdot (j - 1) - (n - i) \cdot a_i)$$ 计算的。

本轮结束后,Codesecrof 管理层公布了参赛者的成绩表。他们决定,如果参与者 di < k,则可以认为该轮对他来说是未评级的。但想象一下,当管理层发现参与者的评级表是动态的时,他们会感到多么惊讶。换句话说,当某个参与者从评级中删除时,他就会从结果表中删除,并根据新表重新计算评级。当然,所有排除评级的申请都会根据当前表格进行考虑。

我们知道,在所有排除评级的申请中,第一个考虑的申请是来自排名最高的参与者(具有最少数量的排名),其中 di < k。我们还知道,所有参与者都提交了排除评级的申请。

现在Sereja想知道,要从比赛评级中排除的参与者人数是多少,以及原始表中的参与者人数按从评级中排除的顺序排列。注意第一个测试用例的分析,以便更好地理解该语句。

输入

第一行包含两个整数n、k (1 ≤ n ≤ 2·105, - 109 ≤ k ≤ 0)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 初始表中参与者的评分。

输出

按照从表中删除的顺序打印参与者的数量。打印参与者的初始编号,即参与者在初始表中的编号。

示例

输入 #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

注意

考虑第一个测试样本。

1. 最初,竞赛参与者的评分顺序为 [5, 3, 4, 1, 2]。您可以使用此序列来计算评级更改的序列:[0, -9, -13, 8, 14]。根据问题陈述,获得第二名的参赛者的申请将被优先考虑。
2. 一旦第二名获得者退出评分,参赛者的评分顺序将等于[5,4,1,2]。通过这个序列,您可以计算新的评级变化序列:[0, -8, 2, 6]。根据问题陈述,获得第二名的参赛者的申请将被考虑。最初,这位参赛者获得了第三名。
3. 新的评级序列等于[5, 1, 2],新的评级变化序列等于[0, -1, 1]。考虑第二名参赛者的申请,最初该参赛者获得第四名。
4. 新的评级序列等于[5, 2],新的评级变化序列等于[0, 0]。将不会考虑更多的申请。

因此,您应该打印 2, 3, 4。