QOJ.ac

QOJ

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

#862. Sprawiedliwość społeczna

Statistics

Wybory lokalne dobiegły końca. Twoje miasto ma nowego burmistrza, a Ty jesteś jego najbardziej zaufanym doradcą! Podczas kampanii zbudowałeś jego popularność na obietnicy zaprowadzenia w mieście sprawiedliwości społecznej. Choć początkowo miało to być tylko hasło, nad którym nie warto się zbytnio rozwodzić, w końcu zostałeś zmuszony przez wszystkich tych wścibskich dziennikarzy do zdefiniowania jego precyzyjnego znaczenia. Wymyśliłeś stałą $K > 1$ i stwierdziłeś, że sprawiedliwość społeczna zostanie osiągnięta, gdy nikt nie zarabia więcej niż $K$ razy średnia płaca mieszkańców miasta.

Teraz nadszedł czas, aby spełnić tę obietnicę. Burmistrz nie ma tak naprawdę żadnego rozsądnego planu, jak wymusić sprawiedliwość społeczną bez załamania gospodarki, ale na szczęście wpadł na znacznie prostszy pomysł. Wystarczy wybrać grupę obywateli, których pensje pasują do definicji... i wygnać wszystkich pozostałych. Doprawdy bezbłędny plan! Ci, którzy pozostaną w mieście, będą żyć w czystym, sprawiedliwym społecznie społeczeństwie. Ci, którzy zostaną wygnani... cóż, i tak nie będą mieli szansy zagłosować w następnych wyborach. Proste i skuteczne – co może pójść nie tak?

Oczywiście nic nie może pójść nie tak, ale dla Ciebie sprawy mogą potoczyć się jeszcze lepiej! Burmistrz jest zdeterminowany, aby wygnać jak najmniej osób, by osiągnąć cel, ale jeśli istnieje więcej niż jeden możliwy sposób, by to zrobić, z pewnością będziesz w stanie wpłynąć na wybór. Jasne jest, że nie zaszkodzi porozmawiać wcześniej z obywatelami i dowiedzieć się, czy niektórzy z nich mają coś ciekawego do zaoferowania w zamian za Twoją ochronę, gdy zapadają decyzje.

Jest jednak pewien haczyk: jeśli nie ma możliwości, aby dana osoba mogła zostać, dyskutowanie o tym z nią byłoby niepotrzebnym i bezsensownym ryzykiem, ponieważ i tak nie mógłbyś zaoferować jej ochrony. Bardziej pragmatycznym wyborem będzie sporządzenie listy wszystkich takich obywateli – i rozmowa ze wszystkimi pozostałymi.

Wejście

Pierwsza linia wejścia zawiera liczbę przypadków testowych $z$ ($1 \le z \le 1000$). Następnie następują opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 200\,000$) – liczbę obywateli. Obywatele są ponumerowani od $1$ do $n$.

Następna linia zawiera $n$ liczb całkowitych $a_i$ ($0 \le a_i \le 10^9$) – pensje obywateli.

Ostatnia linia zawiera dwie liczby całkowite $p$ oraz $q$ ($1 \le q < p \le 1000$), które definiują stałą $K := \frac{p}{q}$.

Całkowita liczba obywateli we wszystkich przypadkach testowych nie przekracza $1\,000\,000$.

Wyjście

Dla każdego przypadku testowego wypisz linię zawierającą liczbę całkowitą $c$ ($0 \le c < n$): liczbę osób, które definitywnie nie mogą pozostać w mieście. Następnie wypisz pojedynczą linię zawierającą $c$ liczb całkowitych: identyfikatory tych obywateli w porządku rosnącym.

Przykład

Wejście 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

Wyjście 1

0
1
2
2
4 5

Uwagi

W pierwszym przypadku testowym cały zbiór nie jest sprawiedliwy społecznie. Można zauważyć, że dla każdego obywatela istnieje sprawiedliwy społecznie zbiór o rozmiarze 3 zawierający tego obywatela. Dlatego ktoś musi zostać wygnany, ale każdy ma szansę nie być tą osobą.

W drugim przypadku testowym dwie osoby muszą zostać wygnane. Istnieją trzy możliwości: obywatele numer 1 i 2 mogą zostać wygnani, albo 2 i 4, albo 2 i 5. Dlatego nie jest możliwe zbudowanie sprawiedliwości z osobą 2 na pokładzie, podczas gdy każdy inny obywatel ma szansę zostać.

W trzecim przypadku obywatele 4 i 5 muszą wyraźnie zostać wygnani – wystarczy spojrzeć na ich oburzające pensje!

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.