Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 تفاعلية
الإحصائيات

Beschreibung

Gegeben ist ein gerichteter Graph mit $n$ Knoten, die von $1$ bis $n$ nummeriert sind. Für jeden Knoten $1 \le i \le n$ beträgt der Ausgangsgrad von Knoten $i$ höchstens eins; daher können wir den Graphen durch ein Array $p_i$ beschreiben, wobei $p_i = 0$ gilt, falls der Ausgangsgrad von Knoten $i$ null ist, und andernfalls $1 \le p_i \le n$, $p_i \ne i$ gilt und eine gerichtete Kante von $i$ nach $p_i$ existiert. Es gibt keine gerichteten Zyklen im Graphen, sodass von jedem Knoten $i$ aus der Pfad, der durch wiederholtes Weiterziehen zum nächsten Knoten entlang gerichteter Kanten entsteht, schließlich an einem Knoten mit Ausgangsgrad null endet.

Anfangs befindet sich ein Holzspielstein auf einem der Knoten. Wenn du in die Hände klatschst und der Spielstein auf einem Knoten $i$ mit $p_i$ ungleich null liegt, bewegt er sich zum Knoten $p_i$; andernfalls bewegt er sich nicht. Allerdings kannst du überhaupt nicht sehen, wo sich der Spielstein befindet — die einzige Operation, die du ausführen kannst, besteht darin, eine Teilmenge von Knoten auszuwählen, den Spielstein auf einen deiner gewählten Knoten zu setzen, einige Male in die Hände zu klatschen und zu beobachten, ob der Spielstein am Ende auf einem deiner gewählten Knoten landet. Sogar die Anfangsposition des Spielsteins und die Anzahl der Klatscher werden vom Interaktor gewählt: Du darfst lediglich die Teilmenge von Knoten auswählen und beobachten, wie oft du maximal in die Hände klatschen kannst, sodass der Spielstein auf einem deiner gewählten Knoten starten und auf einem deiner gewählten Knoten enden kann.

Du möchtest eine einzige Kante von $x$ nach $y$ hinzufügen ($1 \le x, y \le n$, $x \ne y$ und $p_x = 0$, d. h. du darfst $p_x = y$ setzen), sodass du auf dem gesamten Graphen noch öfter in die Hände klatschen kannst als zuvor. Dennoch darf das Hinzufügen der Kante keine gerichteten Zyklen im Graphen erzeugen.

Finde eine beliebige solche Kante, die du hinzufügen kannst, indem du für höchstens $n$ Teilmengen von Knoten die maximale Anzahl an Klatschern abfragst, oder stelle fest, dass es unmöglich ist, eine solche Kante hinzuzufügen.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $n$ ($1 \le n \le 1000$).

Interaktion

Um eine Anfrage zu stellen, gib eine einzelne Zeile der Form $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ aus, wobei $1 \le k \le n$ gilt und $1 \le u_i \le n$ paarweise verschiedene Knoten in deiner gewählten Teilmenge sind. Lies anschließend eine einzelne Zeile mit einer einzelnen ganzen Zahl ein: die maximale Anzahl, wie oft du in die Hände klatschen kannst, sodass der Spielstein auf einem deiner gewählten Knoten starten und auf einem deiner gewählten Knoten enden kann. Du darfst höchstens $n$ Anfragen stellen.

Nachdem du die Kante bestimmt hast, die du hinzufügen möchtest, gib eine einzelne Zeile der Form $\texttt{! } x \text{ } y$ aus, wobei $1 \le x, y \le n$ die Endpunkte der gerichteten Kante sind, die du hinzufügen möchtest. Falls es mehrere Lösungen gibt, kannst du eine beliebige davon ausgeben.

Falls es unmöglich ist, eine solche Kante hinzuzufügen, gib anstelle der Endpunkte der Kante $-1 \text{ -1}$ aus.

Deine Lösung muss sich unmittelbar nach der Ausgabe der Antwort beenden.

Leere den Ausgabepuffer (flush) nach jeder gestellten Anfrage.

Der Interaktor ist nicht adaptiv; der Graph steht im Voraus fest.

Beispiel

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Hinweis

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.