Universal Cup Judging System

Universal Cup

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

題目描述

給定一個包含 $n$ 個頂點的有向圖,頂點編號為 $1$ 到 $n$。對於每個頂點 $1 \le i \le n$,頂點 $i$ 的出度至多為 $1$;因此我們可以用一個陣列 $p_i$ 來描述這個圖:如果頂點 $i$ 的出度為 $0$,則 $p_i = 0$;否則 $1 \le p_i \le n$ 且 $p_i \ne i$,表示存在一條從 $i$ 到 $p_i$ 的有向邊。圖中沒有有向環,因此從任意頂點 $i$ 出發,沿著有向邊不斷移動到下一個頂點所形成的路徑最終都會在一個出度為 $0$ 的頂點處終止。

起初,有一個木製跳棋放在某個頂點上。當你拍手時,如果跳棋所在的頂點 $i$ 滿足 $p_i$ 非零,它就會移動到頂點 $p_i$;否則它保持不動。然而,你完全看不到跳棋在哪裡——你唯一能進行的操作是選擇一個頂點子集,將跳棋放在你選擇的某個頂點上,拍手若干次,並觀察跳棋最終是否停留在你選擇的某個頂點上。甚至跳棋的初始放置位置以及拍手的次數都是由互動器選擇的:你只能選擇頂點子集,並觀察在跳棋能夠從所選子集中的某個頂點出發並最終停留在所選子集中的某個頂點的前提下,你最多可以拍手多少次。

你希望新增一條從 $x$ 到 $y$ 的單向邊(滿足 $1 \le x, y \le n$,$x \ne y$,且 $p_x = 0$,即你可以令 $p_x = y$),使得在整個圖上可以拍手的最大次數比之前嚴格增加。同時,新增這條邊後圖中仍然不能出現任何有向環。

請透過對至多 $n$ 個頂點子集查詢最多可拍手的次數,找出任意一條可以新增的邊,或者判定不可能新增這樣的邊。

輸入格式

輸入的第一行包含一個整數 $n$($1 \le n \le 1000$)。

互動格式

若要發起一次查詢,請輸出一行形如 $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ 的內容,其中 $1 \le k \le n$,且 $1 \le u_i \le n$ 是你所選子集中兩兩不同的頂點。隨後讀取一行,包含一個整數:表示在跳棋能夠從你選擇的某個頂點出發並最終停留在你選擇的某個頂點的前提下,你最多可以拍手的次數。你至多可以進行 $n$ 次查詢。

當你確定了想要新增的邊後,輸出一行形如 $\texttt{! } x \text{ } y$ 的內容,其中 $1 \le x, y \le n$ 是你想要新增的有向邊的兩個端點。如果存在多組解,你可以輸出任意一組。

如果不可能新增這樣的邊,請輸出 $-1 \text{ -1}$ 來代替邊的兩個端點。

輸出答案後,你的程式必須立即終止。

每次發起查詢後,請刷新輸出緩衝區。

互動器是非自適應的;圖在互動開始前就已經固定。

範例

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

說明

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.