#P8832. [传智杯 #3 初赛] 志愿者

[传智杯 #3 初赛] 志愿者

题目描述

传智专修学院总共召集了 nn 位志愿者来负责打扫活动,现在需要你负责帮忙统计每位志愿者的工作情况,用来制作光荣榜,给他们发小花花。

ii 位志愿者有一个工作时长 tit_i ,以及他负责的工作的难度系数 kik_i ,一名志愿者的贡献度可以用 ki×tik_i \times t_i 确定。

现在要为这些志愿者的贡献度从大到小排个序,请你完成这个任务。相同贡献度的志愿者以工作时长较长的排在前面。如果贡献和时长一样,那么编号小的志愿者排在前面。

输入格式

一行一个整数 nn ,表示志愿者的数量。

接下来 nn 行,每行两个使用空格隔开的整数 ti,kit_i,k_i ,表示第 ii 名志愿者的时间和难度系数。

输出格式

一行,共 nn 个整数,第 ii 个数表示排名为 ii 的志愿者的序号,从 11 开始编号。

请注意本题时限为 5s,输入输出规模较大,请注意常数因素对耗时的影响,我们不会给使用 Java 和 Python 的选手增加额外的运行时间。

3
1 2
2 3
3 4
3 2 1

提示

对于 40%40\% 的数据,满足 1n1001 \leq n \leq 100
对于额外 20%20\% 的数据,满足 ki=1k_i=1
对于 100%100\% 的数据,满足 $1 \leq n \leq 5 \times 10^5,1 \leq k_i,t_i \leq 1000$。

然而,由于本次比赛是 ACM 赛制,因此您必须通过 100%100\% 的数据才能够获得本题的得分,后题同。