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.