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 の頂点で停止します。

最初、いずれかの頂点の上に木製のチェッカー(駒)が 1 つ置かれています。あなたが手を叩くと、チェッカーが置かれている頂点 $i$ の $p_i$ が非ゼロであればチェッカーは頂点 $p_i$ に移動し、そうでなければ移動しません。しかし、チェッカーがどこにあるかは全く見えません。あなたが行える唯一の操作は、頂点の部分集合を 1 つ選び、選んだ頂点のいずれかにチェッカーを置き、何回か手を叩いた後、チェッカーが選んだ頂点のいずれかに止まっているかどうかを観察することです。チェッカーの初期配置や手を叩く回数すらジャッジ(インタラクタ)によって選ばれます。あなたができるのは頂点の部分集合を選ぶことと、チェッカーが選んだ頂点のいずれかから出発して選んだ頂点のいずれかで終われるような、手を叩く回数の最大値を観察することだけです。

あなたは頂点 $x$ から頂点 $y$ への有向辺を 1 本追加して(ただし $1 \le x, y \le n$、$x \ne y$、かつ $p_x = 0$、すなわち $p_x = y$ と設定できる)、グラフ全体で手を叩ける最大回数を以前よりもさらに増やしたいと考えています。ただし、辺を追加した後もグラフに有向閉路が生じてはなりません。

高々 $n$ 個の頂点部分集合について手を叩ける最大回数を質問することで、追加できるそのような辺を 1 つ見つけるか、あるいはそのような辺を追加することが不可能であると判定してください。

入力

入力の 1 行目には単一の整数 $n$ ($1 \le n \le 1000$) が与えられます。

相互作用

質問を行うには、$\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ の形式で 1 行出力してください。ここで $1 \le k \le n$ であり、$1 \le u_i \le n$ は選んだ部分集合に含まれる互いに異なる頂点です。その後、1 つの整数を含む 1 行を読み込んでください。この整数は、チェッカーが選んだ頂点のいずれかから出発して選んだ頂点のいずれかで終われるような、手を叩く回数の最大値を表します。質問は高々 $n$ 回まで行うことができます。

追加したい有向辺が特定できたら、端点 $1 \le x, y \le n$ を用いて $\texttt{! } x \text{ } y$ の形式で 1 行出力してください。解が複数存在する場合は、どれを出力しても構いません。

そのような辺を追加することが不可能な場合は、辺の端点の代わりに $-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.