Opis zadania
W prowincji Plang, $n = 300$ uczniów wzięło udział w Plang OI 2026. Wśród nich, niektórzy zdobyli złote medale, a inni nie.
Uczniowie w prowincji Plang mają dziwny zwyczaj. Jeśli nie zdobyli złotego medalu, uczciwie powiedzą, że go nie zdobyli. Jednak jeśli go zdobyli, powiedzą, że go zdobyli z prawdopodobieństwem $p$, a z prawdopodobieństwem $1-p$ powiedzą, że go nie zdobyli. Należy zauważyć, że każda odpowiedź jest losowa i nie ma związku z poprzednią.
Ty, jako trener prowincji Plang, chcesz wiedzieć dla każdego ucznia, czy zdobył złoty medal. Następnie możesz pozwolić Unie wykonać następujące czynności:
- Wybierz kilku różnych uczniów i poproś Unę, aby zapytała każdego z nich, czy zdobył złoty medal. Una powie ci liczbę osób, które odpowiedziały "Tak".
Linia kwalifikacyjna do złotego medalu w Plang OI 2025 wynosiła 571, więc powinieneś znaleźć odpowiedź średnio w nie więcej niż 568 zapytaniach.
Ze względu na ograniczenia Plang OI, możesz założyć, że dokładnie 48 uczniów zdobyło złoty medal.
Obrazek 1: Trener pyta ucznia, ile punktów ukrył.
Interakcja
Jest to problem interaktywny. Pamiętaj, aby opróżnić bufor wyjściowy po każdym wypisaniu. Aby opróżnić wyjście, możesz użyć:
fflush(stdout)lubcout.flush()w C/C++;System.out.flush()w Javie i Kotlin;sys.stdout.flush()w Pythonie.
Najpierw powinieneś odczytać liczbę całkowitą $T$ ($T = 20$), wskazującą liczbę przypadków testowych.
Dla każdego przypadku testowego powinieneś odczytać liczbę całkowitą $n$ ($n = 300$), wskazującą liczbę uczniów.
Aby wykonać zapytanie, powinieneś wypisać jedną linię w formacie ? k P1 P2 ... Pk ($1 \le P_i \le n$, $P_i \ne P_j$ dla $1 < i < j \le k$).
Następnie odczytaj liczbę całkowitą wskazującą odpowiedź, którą znalazła Una. Jeśli twoje zapytanie jest nieprawidłowe, lub jeśli wykonasz więcej niż $568T$ zapytań łącznie, program sędziowski wypisze -1. Po odczytaniu -1 powinieneś natychmiast zakończyć działanie, aby uniknąć niezdefiniowanego zachowania.
Następnie powinieneś wypisać jedną linię w formacie ! s1 s2 ... sn, gdzie $s_i = 1$ oznacza, że $i$-ty uczeń zdobył złoto, w przeciwnym razie $0$.
Następnie odczytaj jedno słowo OK lub WA wskazujące, czy twoja odpowiedź jest poprawna. Jeśli twój program odczyta WA, powinieneś natychmiast zakończyć działanie, aby uniknąć niezdefiniowanego zachowania.
Należy zauważyć, że sędzia nie jest adaptacyjny, co oznacza, że odpowiedź nie zmieni się po twoich zapytaniach. Jest co najwyżej 10 testów.
Przykład
Wejście 1
1 2 0 0 1
Wyjście 1
? 2 1 2 ? 1 1 ? 1 2 ! 0 1
Uwagi
Należy zauważyć, że przykład jest tylko dla odniesienia, nie spełnia $T = 20$ i $n = 300$, i nie pojawi się w ostatecznych testach.
Narzędzie do testowania jest dostarczane, aby pomóc uczestnikom w rozwijaniu i testowaniu ich rozwiązań. Możesz pobrać to narzędzie z załączników. Wykonanie narzędzia z opcją "-h" powinno opisać, jak używać narzędzia. Narzędzie do testowania będzie implementować tylko niektóre scenariusze testowe i tylko niektóre funkcjonalności prawdziwego programu sędziowskiego.