Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] インタラクティブ ハック可能 ✓
統計

問題文

もちろん、これは問題です。

これはインタラクティブな問題です。頂点数 $n$、辺数 $m$ の未知の無向グラフが与えられます。多重辺や自己ループはありません。あなたは毎回、ジャッジに次の質問をすることができます:

  • 頂点集合 $S \subseteq \{1, 2, \dots, n\}$ を指定し、この頂点集合が独立集合であるかどうかを尋ねる。

ここで、独立集合とは、集合 $S$ 内の任意の 2 つの異なる頂点の間に辺が存在しないことを意味します。

あなたの目標は、$M = n + m(2 + \lceil\log_2 n\rceil)$ 回以下の質問を用いて、グラフの辺集合全体を特定することです。

なお、事前に $m$ の値は知らされず、ジャッジは適応的(adaptive)であることに注意してください。すなわち、グラフは最初から固定されているわけではなく、あなたの質問に応じて動的に調整されます。

入力

1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T \le 100$) が与えられます。

各テストケースについて、未知の無向グラフの頂点数を表す整数 $n$ ($1 \le n \le 500$) が 1 行で与えられます。

すべてのテストケースにおける $n$ の総和は $500$ を超えず、$0 \le m \le 500$ であり、$m$ の総和も $500$ を超えないことが保証されます。

入出力

質問を行う際は、次のように 1 行で出力してください:

? k v_1 v_2 ... v_k

ここで、$k$ は頂点集合のサイズを表し、$v_1, v_2, \dots, v_k$ は質問する集合に含まれる頂点の番号であり、互いに異なる必要があります。

ジャッジは整数を 1 つ返します:頂点集合が独立集合であれば $1$、そうでなければ $0$ です。

グラフのすべての辺を特定したら、次のように 1 行で出力してください:

! m u_1 v_1 u_2 v_2 ... u_m v_m

ここで、$m$ は無向グラフの辺数であり、$(u_i, v_i)$ はグラフの辺を表します。辺は任意の順序で出力して構いません。

その後、残りのテストケースがなければプログラムを直ちに終了し、そうでなければ次のテストケースの処理に進んでください。

入力例

入力例 1

1
4
0
1
0
0
1
0

出力例 1

? 2 1 2
? 2 1 3
? 2 1 4
? 2 2 3
? 2 2 4
? 2 3 4
! 4 1 2 2 3 3 4 1 4

入出力例の説明

出力例は、各辺が存在するかどうかを個別に質問する対話プロセスを示しています。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1842EditorialOpenNew Editorial for Problem #18123wangmaruiView

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.