問題一覧 > 通常問題

No.2453 Seat Allocation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 99
作問者 : srjywrdnprkt / テスター : 👑 p-adic
1 ProblemId : 10016 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-21 23:47:28

問題文

yuki国には 1,2,⋯ ,N1, 2, \cdots, N と番号がついた NN 個の政党があります。それぞれの政党には 1,2,⋯ ,101001, 2, \cdots, 10^{100} と番号がついた 1010010^{100} 人の候補者が属しています。

今回の選挙で政党 ii は AiA_i 票を獲得しました。この結果に基づいて、あなたは以下のルールに従って MM 人の当選者を決定しようとしています。ただし、B=(B1,B2,⋯ ,BM)B=(B_1, B_2, \cdots, B_M) は狭義単調増加な正整数列です。

  1. 1≤j≤M1\leq j \leq M を満たす jj について、政党 ii の jj 番目の候補者にはスコア Pij=AiBjP_{ij}=\displaystyle\frac{A_i}{B_j} が与えられる。それ以外の候補者のスコアは 00 とする。
  2. スコア PijP_{ij} が大きい候補者から順に当選させる。ただし、スコアが同じ候補者が複数いる場合は、所属している政党の番号が小さいものから順に当選させる。
k=1,⋯Mk=1, \cdots M のそれぞれについて、kk 番目に当選した候補者が属している政党の番号を求めてください。

入力

N MN\ M
A1 ⋯ ANA_1\ \cdots\ A_N
B1 ⋯ BMB_1\ \cdots\ B_M

入力は全て整数で以下の制約を満たす。

  • 2≤N≤1052\leq N \leq 10^{5}
  • 1≤M≤1051\leq M \leq 10^{5}
  • 1≤Ai≤1091\leq A_i \leq 10^9
  • 1≤B1<B2<⋯<BM≤1091 \leq B_1 < B_2 < \cdots < B_M \leq 10^9

出力

MM 行出力してください。kk 行目には kk 番目の当選者が所属している政党の番号を出力してください。

サンプル

サンプル1
入力
3 5
180 120 90
1 2 3 4 5
出力
1
2
1
3
1

各政党の MM 番目までの候補者のスコアは以下のようになります。

  • 政党 11 ⋯\cdots (180,90,60,45,36)(180, 90, 60, 45, 36)
  • 政党 22 ⋯\cdots (120,60,40,30,24)(120, 60, 40, 30, 24)
  • 政党 33 ⋯\cdots (90,45,30,22.5,18)(90, 45, 30, 22.5, 18)

11 番目の当選者は最も大きいスコアを持つ政党 11 の 11 番目の候補者、 22 番目の当選者は 22 番目に大きいスコアを持つ政党 22 の 11 番目の候補者です。

33 番目に大きいスコアは 9090 であり、それを持つ候補者は政党 22 の 22 番目の 候補者と政党 33 の 11 番目の候補者です。この場合、政党の番号が小さい政党 11 の候補者が先に当選し、政党 33 の候補者はその次に当選します。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。