codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1978D.md (3191B)


      1 Source: https://codeforces.com/problemset/problem/1978/D
      2 
      3 D. Elections
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Elections are taking place in Berland. There are $n$ candidates participating in the elections, numbered from $1$ to $n$. The $i$-th candidate has $a_i$ fans who will vote for him. Additionally, there are $c$ people who are undecided about their favorite candidate, let's call them undecided. Undecided people will vote for the candidate with the lowest number.
     22 
     23 The candidate who receives the maximum number of votes wins the elections, and if multiple candidates receive the same maximum number of votes, the candidate with the lowest number among them wins.
     24 
     25 You found these elections too boring and predictable, so you decided to exclude some candidates from them. If you do not allow candidate number $i$ to participate in the elections, all $a_i$ of his fans will become undecided, and will vote for the candidate with the lowest number.
     26 
     27 You are curious to find, for each $i$ from $1$ to $n$, the minimum number of candidates that need to be excluded from the elections for candidate number $i$ to win the elections.
     28 
     29 Input
     30 
     31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $c$ ($1 \le n \le 2 \cdot 10^5$, $0 \le c \le 10^9$) — the number of candidates in the elections and the number of undecided people.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the number of fans for each candidate.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output $n$ integers, the $i$-th of which should be equal to the minimum number of candidates that need to be excluded from the elections for candidate number $i$ to win.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 3 1
     51 
     52 2 0 3
     53 
     54 2 3
     55 
     56 0 10
     57 
     58 5 3
     59 
     60 5 4 3 2 1
     61 
     62 4 5
     63 
     64 3 10 7 1
     65 
     66 6 0
     67 
     68 2 2 2 3 3 3
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 0 1 2
     75 1 0
     76 0 1 2 3 4
     77 1 0 2 3
     78 1 1 2 0 4 5
     79 ```
     80 
     81 Note
     82 
     83 In the first test case:
     84 
     85 * If all candidates are allowed, candidate number $1$ will receive $3$ votes ($1$ undecided person will vote for him), candidate number $2$ will receive $0$ votes, and candidate number $3$ will receive $3$ votes. Therefore, candidate number $1$ wins (he received the same number of votes as candidate $3$, but his number is lower), so the answer for him is $0$.
     86 * If candidate number $1$ is not allowed, his $2$ fans will become undecided. Then candidate number $2$ will receive $3$ votes ($3$ undecided people will vote for him) and candidate number $3$ will receive $3$ votes. Therefore, candidate number $2$ wins (he received the same number of votes as candidate $3$, but his number is lower), so the answer for him is $1$.
     87 * If candidates with numbers $1$ and $2$ are not allowed, candidate number $3$ wins, so the answer for him is $2$.
     88 
     89 In the second test case, candidate number $1$ will win if candidate number $2$ is not allowed to participate.