Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 交互
统计

Описание

Дан ориентированный граф на $n$ вершинах, пронумерованных от $1$ до $n$. Для каждой вершины $1 \le i \le n$ полустепень исхода вершины $i$ не превосходит единицы; таким образом, мы можем описать граф с помощью массива $p_i$, где $p_i = 0$, если полустепень исхода вершины $i$ равна нулю, а иначе $1 \le p_i \le n$, $p_i \ne i$, и существует ориентированное ребро из $i$ в $p_i$. В графе нет ориентированных циклов, поэтому из любой вершины $i$ путь, образованный последовательным переходом к следующей вершине по ориентированным рёбрам, в конечном счёте завершится в вершине с нулевой полустепенью исхода.

Изначально на одной из вершин стоит деревянная шашка. Когда вы хлопаете в ладоши, если шашка находится в вершине $i$ с ненулевым $p_i$, она перемещается в вершину $p_i$; в противном случае она остаётся на месте. Однако вы совершенно не видите, где находится шашка — единственная доступная вам операция состоит в том, чтобы выбрать подмножество вершин, поставить шашку на одну из выбранных вершин, хлопнуть в ладоши некоторое количество раз и увидеть, окажется ли шашка в итоге на одной из выбранных вершин. Даже начальное положение шашки и количество хлопков выбираются интерактором: вы можете лишь выбрать подмножество вершин и узнать максимальное количество хлопков, при котором шашка может начать движение в одной из выбранных вами вершин и закончить его в одной из выбранных вами вершин.

Вы хотите добавить одно ребро из $x$ в $y$ ($1 \le x, y \le n$, $x \ne y$ и $p_x = 0$, то есть можно положить $p_x = y$), чтобы на всём графе можно было хлопнуть в ладоши ещё больше раз, чем раньше. При этом добавление ребра не должно создавать ориентированных циклов в графе.

Найдите любое такое ребро, которое можно добавить, сделав запросы о максимальном количестве хлопков не более чем для $n$ подмножеств вершин, или определите, что добавить такое ребро невозможно.

Входные данные

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 1000$).

Взаимодействие

Чтобы сделать запрос, выведите одну строку вида $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, где $1 \le k \le n$, а $1 \le u_i \le n$ — попарно различные вершины в выбранном вами подмножестве. Затем считайте одну строку, содержащую одно целое число: максимальное количество раз, которое вы можете хлопнуть в ладоши так, чтобы шашка могла начать путь в одной из выбранных вершин и закончить его в одной из выбранных вершин. Вы можете сделать не более $n$ запросов.

После того как вы определили ребро, которое хотите добавить, выведите одну строку вида $\texttt{! } x \text{ } y$, где $1 \le x, y \le n$ — концы ориентированного ребра, которое вы хотите добавить. Если решений несколько, вы можете вывести любое из них.

Если добавить такое ребро невозможно, выведите $-1 \text{ -1}$ вместо концов ребра.

Ваше решение должно немедленно завершиться после вывода ответа.

Сбрасывайте буфер вывода (flush) после каждого сделанного запроса.

Интерактор не адаптивен; граф зафиксирован заранее.

Пример

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.