No.2453 Seat Allocation
タグ : / 解いたユーザー数 97
作問者 :
srjywrdnprkt
/ テスター :
👑 
p-adic
問題文
yuki国には $1, 2, \cdots, N$ と番号がついた $N$ 個の政党があります。それぞれの政党には $1, 2, \cdots, 10^{100}$ と番号がついた $10^{100}$ 人の候補者が属しています。
今回の選挙で政党 $i$ は $A_i$ 票を獲得しました。この結果に基づいて、あなたは以下のルールに従って $M$ 人の当選者を決定しようとしています。ただし、$B=(B_1, B_2, \cdots, B_M)$ は狭義単調増加な正整数列です。
- $1\leq j \leq M$ を満たす $j$ について、政党 $i$ の $j$ 番目の候補者にはスコア $P_{ij}=\displaystyle\frac{A_i}{B_j}$ が与えられる。それ以外の候補者のスコアは $0$ とする。
- スコア $P_{ij}$ が大きい候補者から順に当選させる。ただし、スコアが同じ候補者が複数いる場合は、所属している政党の番号が小さいものから順に当選させる。
入力
$N\ M$ $A_1\ \cdots\ A_N$ $B_1\ \cdots\ B_M$
入力は全て整数で以下の制約を満たす。
- $2\leq N \leq 10^{5}$
- $1\leq M \leq 10^{5}$
- $1\leq A_i \leq 10^9$
- $1 \leq B_1 < B_2 < \cdots < B_M \leq 10^9$
出力
$M$ 行出力してください。$k$ 行目には $k$ 番目の当選者が所属している政党の番号を出力してください。
サンプル
サンプル1
入力
3 5 180 120 90 1 2 3 4 5
出力
1 2 1 3 1
各政党の $M$ 番目までの候補者のスコアは以下のようになります。
- 政党 $1$ $\cdots$ $(180, 90, 60, 45, 36)$
- 政党 $2$ $\cdots$ $(120, 60, 40, 30, 24)$
- 政党 $3$ $\cdots$ $(90, 45, 30, 22.5, 18)$
$1$ 番目の当選者は最も大きいスコアを持つ政党 $1$ の $1$ 番目の候補者、 $2$ 番目の当選者は $2$ 番目に大きいスコアを持つ政党 $2$ の $1$ 番目の候補者です。
$3$ 番目に大きいスコアは $90$ であり、それを持つ候補者は政党 $2$ の $2$ 番目の 候補者と政党 $3$ の $1$ 番目の候補者です。この場合、政党の番号が小さい政党 $1$ の候補者が先に当選し、政党 $3$ の候補者はその次に当選します。
サンプル2
入力
3 3 1000 10000 100000 1 100000000 1000000000
出力
3 2 1
サンプル3
入力
2 4 499999319 999998638 499999321 999998642 999999999 1000000000
出力
2 1 2 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。