B - Best Strategy Editorial /

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