시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 36 | 19 | 18 | 56.250% |
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:
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
".
5 10 30 10 5 3 1 3
3 5 2 1 4
5 5 20 5 3 3 3 3
impossible
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2020 F번
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 3: Nordic+ Contest 2020 F번