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.