Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Interactive
Statistics

Beskrivning

Det finns en riktad graf med $n$ hörn numrerade från $1$ till $n$. För varje hörn $1 \le i \le n$ är utgraden för hörn $i$ högst ett; därmed kan vi beskriva grafen med en array $p_i$, där $p_i = 0$ om utgraden för hörn $i$ är noll, och annars $1 \le p_i \le n$, $p_i \ne i$, och det finns en riktad kant från $i$ till $p_i$. Det finns inga riktade cykler i grafen, så från vilket hörn $i$ som helst kommer vägen som bildas genom att upprepade gånger gå till nästa hörn längs riktade kanter till slut att sluta i ett hörn med utgrad noll.

Från början ligger en träbricka på ett av hörnen. När du klappar i händerna flyttas brickan till hörn $p_i$ om den befinner sig på ett hörn $i$ med $p_i$ skilt från noll; annars flyttas den inte. Du kan dock inte alls se var brickan är — den enda operationen du kan utföra är att välja en delmängd av hörn, placera brickan på ett av dina valda hörn, klappa i händerna ett antal gånger och observera om brickan slutar på ett av dina valda hörn. Till och med brickans startposition och antalet gånger du klappar i händerna väljs av en interaktor: du får bara välja delmängden av hörn och observera det maximala antalet gånger du kan klappa i händerna så att brickan kan starta på ett av dina valda hörn och sluta på ett av dina valda hörn.

Du vill lägga till en enda kant från $x$ till $y$ ($1 \le x, y \le n$, $x \ne y$ och $p_x = 0$, dvs. du kan sätta $p_x = y$), så att du kommer att kunna klappa i händerna ännu fler gånger på hela grafen än tidigare. Att lägga till kanten får dock inte skapa några riktade cykler i grafen.

Hitta en sådan kant som du kan lägga till genom att fråga efter det maximala antalet gånger du kan klappa i händerna på högst $n$ delmängder av hörn, eller avgör att det är omöjligt att lägga till en sådan kant.

Indata

Den första raden i indata innehåller ett enda heltal $n$ ($1 \le n \le 1000$).

Interaktion

För att ställa en fråga, skriv ut en enda rad på formen $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, där $1 \le k \le n$, och $1 \le u_i \le n$ är parvis olika hörn i din valda delmängd. Läs sedan en enda rad som innehåller ett enda heltal: det maximala antalet gånger du kan klappa i händerna så att brickan kan starta på ett av dina valda hörn och sluta på ett av dina valda hörn. Du får ställa högst $n$ frågor.

När du har bestämt vilken kant du vill lägga till, skriv ut en enda rad på formen $\texttt{! } x \text{ } y$, där $1 \le x, y \le n$ är ändpunkterna för den riktade kant du vill lägga till. Om det finns flera lösningar kan du skriva ut vilken som helst av dem.

Om det är omöjligt att lägga till en sådan kant, skriv ut $-1 \text{ -1}$ istället för kantens ändpunkter.

Din lösning måste avslutas omedelbart efter att svaret har skrivits ut.

Töm utdatabufferten (flush) efter varje fråga du ställer.

Interaktorn är inte adaptiv; grafen är fastställd i förväg.

Exempel

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Notering

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.