Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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