Problem C
Tvær Vikur
Languages
en
is
‘Alright boys, where we dropping in?’ can be heard from
Benni’s headphones. He groans and tries to focus on the task at
hand. Benni is competing in the game ‘Two weeks’. On the
sideline sits Arnar who’s paying close attention. Arnar is
quite into betting and knows no better feeling than that from
winning a bet. He wonders in what place each contestant could
end up in so he can make the right bets.
As of right now there are $n$ contestants. Contestant
$i$ has $a_ i$ health points left. If two of
them run into one another, they fight and both lose
$B$ hit points. If one of
them has no hit points left he loses. Note that both
contestants could lose at the same time. If there are
$H$ others left alive when
a contestant loses, that contestant ends up in place
$H + 1$. If a contestant
survives the fight he goes his own way afterwards and fights
next when he encounters someone, possibly the same opponent
again.
Contestants can run into one another in any order. Arnar now wants to know, for each contestant, what is the highest place they could end up in across all possible combinations of encounters.
Input
The first line of the input contains two integers $1 \leq n \leq 10^5$ and $1 \leq B \leq 10^9$. The next line contains $n$ integers $1 \leq a_1, a_2, \dots , a_ n \leq 10^9$, with one space between each pair of adjacent numbers.
Output
Print $b_1, b_2, \dots , b_ n$ with a single space between adjacent numbers where $b_ i$ is the highest place contestant number $i$ can achieve.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$n \leq 3$ |
|
2 |
30 |
$n \leq 10^3$ |
|
3 |
50 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 4 2 3 |
1 1 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 1 2 3 7 |
2 2 2 1 |
