配点 : 300 点
問題文
1 减去 N 包含 N 道题目问题,你将参与使用这些题目的游戏。
在该游戏中,你要对题目 1 道进行回答。 你可以自由选择回答题目的顺序。 题目 i 的回答将以 P_i % 的概率正确。 如果回答正确,你将 S_i 获得点数后,(如果还有未回答的测验)将移至下一个测验的回答。 如果未答对,游戏将立即结束,无法回答剩余的测验。
你希望最大化获得分数总和的期望值。 请找出为实现这一目标的策略(即回答测验的顺序)。 各测验答对与否的概率相互之间都是独立的。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9
- 0 \leq P_i \leq 100
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N S_1 P_1 S_2 P_2 \vdots S_N P_N
出力
按以下格式输出您的答案。
x_1 x_2 \cdots x_N
这里 x_i 表示,如果最初的(i-1)题答对了, i 表示第几题测验将被回答的编号。 如果解答有多个,输出其中任意一个均视为正确。
入力例 1
2 1000 10 300 50
出力例 1
2 1
如果按照测验 1,2 的顺序回答,获得的分数总和的期望值将是 115 。 测验 2,1 的顺序回答,获得的分数总和的期望值将是 200 。 因此,按照测验 2,1 的顺序回答是最优策略。
入力例 2
6 1 0 1 20 1 40 1 60 1 80 1 100
出力例 2
6 5 4 3 2 1
入力例 3
9 88994950 78 405248480 35 561113280 28 22802150 2 946582650 25 201425280 52 669650 41 128877450 71 1396050 25
出力例 3
1 5 8 2 3 6 4 7 9