Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 互動
统计

題目描述

給定一個有 $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.