問題一覧 > 通常問題

No.2453 Seat Allocation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 100
作問者 : srjywrdnprkt / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10016 / 自分の提出
問題文最終更新日: 2023-08-21 23:47:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 403 (順位表) の他の問題:

Problem Statement

The country of yuki has $N$ political parties numbered $1, 2, \cdots, N$. Each party has $10^{100}$ candidates numbered $1, 2, \cdots, 10^{100}$.

In this election, party $i$ received $A_i$ votes. Based on this result, you are going to determine $M$ winners according to the rules below. Here, $B=(B_1, B_2, \cdots, B_M)$ is a strictly increasing sequence of positive integers.

  1. For each $j$ satisfying $1\leq j \leq M$, the $j$-th candidate of party $i$ is given the score $P_{ij}=\displaystyle\frac{A_i}{B_j}$. The score of every other candidate is $0$.
  2. Candidates are elected in descending order of score $P_{ij}$. If multiple candidates have the same score, they are elected in ascending order of the number of the party they belong to.
For each of $k=1, \cdots M$, find the number of the party to which the $k$-th elected candidate belongs.

Input

$N\ M$
$A_1\ \cdots\ A_N$
$B_1\ \cdots\ B_M$

All inputs are integers and satisfy the following constraints.

  • $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$

Output

Print $M$ lines. On the $k$-th line, print the number of the party to which the $k$-th winner belongs.

Sample

Sample 1
Input
3 5
180 120 90
1 2 3 4 5
Output
1
2
1
3
1

The scores of the first $M$ candidates of each party are as follows.

  • Party $1$ $\cdots$ $(180, 90, 60, 45, 36)$
  • Party $2$ $\cdots$ $(120, 60, 40, 30, 24)$
  • Party $3$ $\cdots$ $(90, 45, 30, 22.5, 18)$

The $1$-st winner is the $1$-st candidate of party $1$, who has the largest score, and the $2$-nd winner is the $1$-st candidate of party $2$, who has the $2$-nd largest score.

The $3$-rd largest score is $90$, and the candidates having it are the $2$-nd candidate of party $2$ and the $1$-st candidate of party $3$. In this case, the candidate of party $1$, which has the smaller party number, is elected first, and the candidate of party $3$ is elected next.

Sample 2
Input
3 3
1000 10000 100000
1 100000000 1000000000
Output
3
2
1

Sample 3
Input
2 4
499999319 999998638
499999321 999998642 999999999 1000000000
Output
2
1
2
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。