QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#862. 社会正义

Statistics

地方选举结束了。你的城镇选出了一位新市长,而你是他最信任的顾问!在竞选期间,你曾以“为城镇带来社会正义”作为口号来提升他的声望。最初你只是把这当作一句不必深究的口号,但最终你被那些讨厌的记者逼着给出了精确的定义。你提出了一个常数 $K > 1$,并宣称当没有人赚取的薪水超过城镇居民平均薪水的 $K$ 倍时,社会正义就实现了。

现在是兑现承诺的时候了。市长并没有什么合理的计划来在不导致经济崩溃的情况下强制执行社会正义,但谢天谢地,他想出了一个更简单的办法。只需要选择一组薪水符合定义的市民……然后驱逐其他人即可。这确实是一个完美的计划!留在城镇里的人将生活在一个纯粹、社会公正的社会中。至于那些被驱逐的人……好吧,反正他们在下次选举中也没有投票机会了。简单有效——能出什么差错呢?

当然,什么都不会出错,但对你来说,事情可以变得更好!市长决心为了实现目标而尽可能少地驱逐人口,但如果存在多种实现方式,你肯定能影响他的选择。显然,提前与市民交谈,看看他们中是否有人能在决策时提供一些有价值的东西来换取你的保护,这并没有什么坏处。

不过这里有个问题:如果某个人根本不可能被允许留下,那么与他们讨论就是一种不必要的、毫无意义的风险,因为无论如何你都无法为他们提供保护。一个更务实的选择是列出所有这样的市民——然后与其他人交谈。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 1000$)。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 200\,000$),表示市民的人数。市民编号从 $1$ 到 $n$。 下一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^9$),表示市民的薪水。 最后一行包含两个整数 $p$ 和 $q$ ($1 \le q < p \le 1000$),定义了常数 $K := \frac{p}{q}$。 所有测试用例的市民总数不超过 $1\,000\,000$。

输出格式

对于每个测试用例,输出一行包含一个整数 $c$ ($0 \le c < n$):绝对无法留在城镇中的人数。然后输出一行包含 $c$ 个整数:这些市民的编号,按升序排列。

样例

输入 1

3
4
1 2 3 4
3 2
5
1 15 2 5 1
2 1
5
1 2 3 1000 10000
4 3

输出 1

0
1
2
2
4 5

说明

在第一个测试用例中,整个集合不是社会公正的。可以看出,对于每个市民,都存在一个包含该市民且大小为 $3$ 的社会公正集合。因此,必须有人被驱逐,但每个人都有机会不成为那个被驱逐的人。

在第二个测试用例中,必须驱逐两个人。有三种可能性:驱逐 $1$ 号和 $2$ 号市民,或者 $2$ 号和 $4$ 号,或者 $2$ 号和 $5$ 号。因此,不可能在保留 $2$ 号的情况下建立社会正义,而其他每个市民都有机会留下。

在第三个测试用例中,显然必须驱逐 $4$ 号和 $5$ 号市民——看看他们那离谱的薪水就知道了!

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#187EditorialOpen题解jiangly2025-12-12 23:59:01View

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.