Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Interactive Hackable ✓
Statistics

題目描述

當然,呢個係一道題。

呢個係一道交互題。俾你一個有 $n$ 個頂點同 $m$ 條邊嘅未知無向圖,圖入面冇重邊或者自環。每次你可以向交互庫問以下問題:

  • 俾定一個頂點集合 $S \subseteq \{1, 2, \dots, n\}$,詢問呢個頂點集合係咪一個獨立集。

喺度,獨立集嘅意思係集合 $S$ 入面任意兩個唔同頂點之間都冇邊相連。

你嘅目標係用唔超過 $M = n + m(2 + \lceil\log_2 n\rceil)$ 次詢問嚟確定成張圖嘅所有邊。

請注意,你事先並唔知道 $m$ 嘅值,而且交互庫係自適應(adaptive)嘅,即係張圖喺一開始並唔係固定嘅,而係會根據你嘅詢問動態調整。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 100$),表示測試數據嘅組數。

對於每組測試數據,一行包含一個整數 $n$ ($1 \le n \le 500$),表示呢張未知無向圖嘅頂點數。

保證所有測試數據入面 $n$ 嘅總和唔超過 $500$,$0 \le m \le 500$,而且 $m$ 嘅總和唔超過 $500$。

交互格式

當你需要進行詢問時,輸出一行:

? k v_1 v_2 ... v_k

其中 $k$ 表示頂點集合嘅大細,$v_1, v_2, \dots, v_k$ 係你所詢問嘅集合入面嘅頂點編號,佢哋兩兩唔同。

交互庫會返回一個整數:如果呢個頂點集合係獨立集,就返回 $1$;否則返回 $0$。

當你確定咗圖入面嘅所有邊時,輸出一行:

! 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.