← 返回题目列表

AtCoder · abc308_c

F. 积分榜

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

分数: 300 点

问题陈述

N 人数 1 通过 N 扔了几次硬币。 我们认识那个人 i的抛掷导致 A_i 头和 B_i 尾巴。

人 i的 成功率 抛掷的 定义为 \displaystyle\frac{A_i}{A_i+B_i}。 对人进行排序 1,\ldots,N 按其成功率的降序排列,打破平局的则按其指定号码的升序排列。

约束

  • 2\leq N \leq 2\times 10^5
  • 0\leq A_i, B_i\leq 10^9
  • A_i+B_i \geq 1
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
\vdots
A_N B_N

输出

打印人数 1,\ldots,N 按其成功率的降序排列,打破平局的则按其指定号码的升序排列。


示例输入 1

3
1 3
3 1
2 2

示例输出 1

2 3 1

人 1的成功率为 0.25, 人 2是 0.75和人 3是 0.5.

按成功率的降序对它们进行排序,以获得样本输出中的顺序。


示例输入 2

2
1 3
2 6

示例输出 2

1 2

注意那个人 1 和 2 应按其编号的升序打印,因为它们具有相同的成功率。


示例输入 3

4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

示例输出 3

3 1 4 2