Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 インタラクティブ
統計

Opis

Dany jest graf skierowany o $n$ wierzchołkach ponumerowanych od $1$ do $n$. Dla każdego wierzchołka $1 \le i \le n$, stopień wyjściowy wierzchołka $i$ wynosi co najwyżej jeden; możemy zatem opisać graf za pomocą tablicy $p_i$, gdzie $p_i = 0$, jeśli stopień wyjściowy wierzchołka $i$ wynosi zero, a w przeciwnym razie $1 \le p_i \le n$, $p_i \ne i$ oraz istnieje krawędź skierowana z $i$ do $p_i$. W grafie nie ma cykli skierowanych, więc z dowolnego wierzchołka $i$ ścieżka utworzona przez wielokrotne przechodzenie do następnego wierzchołka wzdłuż krawędzi skierowanych ostatecznie zakończy się w wierzchołku o stopniu wyjściowym równym zero.

Początkowo na jednym z wierzchołków znajduje się drewniany pionek. Kiedy klaśniesz w dłonie, jeśli pionek znajduje się na wierzchołku $i$ o niezerowym $p_i$, przesunie się on na wierzchołek $p_i$; w przeciwnym razie nie porusza się. Nie widzisz jednak, gdzie znajduje się pionek — jedyną operacją, jaką możesz wykonać, jest wybranie podzbioru wierzchołków, umieszczenie pionka na jednym z wybranych wierzchołków, klaśnięcie w dłonie pewną liczbę razy i zaobserwowanie, czy pionek zakończy ruch na jednym z wybranych przez ciebie wierzchołków. Nawet początkowe położenie pionka oraz liczba klaśnięć są wybierane przez interaktora: ty możesz jedynie wybrać podzbiór wierzchołków i zaobserwować maksymalną liczbę klaśnięć, przy której pionek może wystartować z jednego z wybranych wierzchołków i zakończyć ruch na jednym z wybranych wierzchołków.

Chciałbyś dodać pojedynczą krawędź z $x$ do $y$ ($1 \le x, y \le n$, $x \ne y$ oraz $p_x = 0$, tzn. możesz ustawić $p_x = y$), tak abyś mógł klasnąć w dłonie na całym grafie jeszcze więcej razy niż dotychczas. Dodanie tej krawędzi nie może jednak utworzyć żadnego cyklu skierowanego w grafie.

Znajdź dowolną taką krawędź, którą można dodać, pytając o maksymalną liczbę klaśnięć dla co najwyżej $n$ podzbiorów wierzchołków, lub stwierdź, że dodanie takiej krawędzi jest niemożliwe.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 1000$).

Interakcja

Aby zadać zapytanie, wypisz pojedynczy wiersz w postaci $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, gdzie $1 \le k \le n$, a $1 \le u_i \le n$ to parami różne wierzchołki w wybranym podzbiorze. Następnie wczytaj pojedynczy wiersz zawierający jedną liczbę całkowitą: maksymalną liczbę klaśnięć w dłonie, przy której pionek może rozpocząć i zakończyć ruch na wierzchołkach z wybranego podzbioru. Możesz zadać co najwyżej $n$ zapytań.

Po ustaleniu krawędzi, którą chcesz dodać, wypisz pojedynczy wiersz w postaci $\texttt{! } x \text{ } y$, gdzie $1 \le x, y \le n$ to końce skierowanej krawędzi, którą chcesz dodać. Jeśli istnieje wiele rozwiązań, możesz wypisać dowolne z nich.

Jeśli dodanie takiej krawędzi jest niemożliwe, wypisz $-1 \text{ -1}$ zamiast końców krawędzi.

Twoje rozwiązanie musi zakończyć działanie natychmiast po wypisaniu odpowiedzi.

Opróżniaj bufor wyjścia (flush) po każdym zadanym zapytaniu.

Interaktor nie jest adaptacyjny; graf jest ustalony z góry.

Przykład

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Uwaga

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

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.