QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 512 MB 満点: 100

#862. 社會正義

統計

地方選舉結束了。你的城鎮選出了新市長,而你是他最信任的顧問!在競選期間,你以「為城鎮帶來社會正義」的承諾建立了他的聲望。起初,你只是將其視為一個不必深究的口號,但最終,你被迫在那些討厭的記者面前定義其確切含義。你提出了一個常數 $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.