QOJ.ac

QOJ

时间限制: 2 s 内存限制: 512 MB 总分: 100

#880. 影评人

统计

备受期待的动作电影《No Thyme to Fry》即将上映,现在是时候安排影评人进行提前观影并撰写影评了。一家小型电影院被选中用于这些提前放映。

共有 $n$ 名影评人(编号从 $1$ 到 $n$)被安排提前观影,且每人将单独观影。观影后,他们会立即给出 $0$ 到 $m$ 之间的评分。电影院老板 Susan 仔细研究了每位影评人的社交媒体,已经知道第 $i$ 位影评人认为这部电影的初始评分是 $a_i$。然而,第 $i$ 位影评人并不会像你预期的那样直接给出 $a_i$ 的评分,因为他们还会考虑其他影评人给出的分数。他们的行为准则如下:

  1. 第一位到达的影评人会因为能率先观看电影而感到非常高兴,因此无论其初始意见如何,他们都会给出 $m$ 分。
  2. 随后到达的每一位影评人都会查看之前所有影评人给出的平均分。如果该平均分小于或等于他们的初始意见 $a_i$,则该影评人会给出 $a_i$ 分,否则他们会给出 $0$ 分。

Susan 认为影评人们的行为很荒谬。她已经看过这部电影,认为它显然应该得到恰好 $k/n$ 的分数,不多不少!但 Susan 是电影院的老板,所以她可以决定邀请影评人的顺序。你的任务是找到一个 $1, 2, \dots, n$ 的排列,使得如果影评人按此顺序到达,最终的平均分恰好为 $k/n$。

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^4, 0 \le k \le n \cdot m$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le m$,对于每个 $i$),即上述每位影评人的初始评分。

输出格式

如果可以按某种顺序安排影评人,使得最终的平均分恰好为 $k/n$,则输出 $n$ 个整数 $p_1, \dots, p_n$ ($1 \le p_i \le n$),其中 $p_i$ 表示第 $i$ 位到达电影院的影评人编号。该整数列表应为一个排列,使得影评人给出的平均分为 $k/n$。如果存在多种解,输出任意一个即可。

否则,如果不存在这样的顺序,输出 “impossible”。

样例

样例输入 1

5 10 30
10 5 3 1 3

样例输出 1

3 5 2 1 4

样例输入 2

5 5 20
5 3 3 3 3

样例输出 2

impossible

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.