Problem F
Film Critics

Picture by Mattias Ek, cc by
The premier of the anticipated action film No Thyme to Fry is right around the corner, and it is time to give early screenings to film critics so that they can review it. A small cinema has been selected to show these early screenings.

There are $n$ critics numbered from $1$ to $n$ scheduled to watch the movie early, and each of them will watch it separately. After watching it, they will immediately give it a score from $0$ to $m$. Susan, the cinema owner, has carefully looked at every critic’s social media and already knows that the $i$th critic thinks the movie is worth a score of $a_ i$. However, the $i$th critic will not simply give the movie a score of $a_ i$ like you would expect, because they also take into account the scores that the other critics gave. Here is how they behave:

  1. The first critic to arrive will be so happy that they are the first to review the movie that they will give it a score of $m$ regardless of their initial opinion.

  2. Every subsequent critic will look at the average score given by the previous critics. If this number is smaller than or equal to the initial opinion $a_ i$ then the critic will give it a score of $m$, otherwise they will give it a $0$.

Susan thinks the critics’ behaviour is ridiculous. She has watched the movie, and it is clearly worth a score of exactly $k/n$ and nothing else! But Susan is the owner of the cinema, so she gets to decide in what order to invite the critics. Your task is to find a permutation of $1,2, \dots , n$ so that if the critics arrive in this order the average score will be exactly $k/n$.


The first line of input contains three integers $n$, $m$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 10^4$, $0 \leq k \leq n \cdot m$). The second line contains the $n$ integers $a_1, a_2, \ldots , a_ n$ ($0 \le a_ i \le m$ for each $i$), the $n$ critic scores as described above.


If the critics can be ordered in such a way that the resulting average score is exactly $k/n$, then output $n$ integers $p_1, \ldots , p_ n$ ($1 \le p_ i \le n$), where $p_ i$ indicates that the $i$th critic to visit the cinema is the critic numbered $p_ i$. This list of integers should be a permutation such that the average score given by the critics is $k/n$. If there are multiple solutions any one will be accepted.

Otherwise, if there is no such way to order the critics, output “impossible”.

Sample Input 1 Sample Output 1
5 10 30
10 5 3 1 3
3 5 2 1 4 
Sample Input 2 Sample Output 2
5 5 20
5 3 3 3 3

Please log in to submit a solution to this problem

Log in