Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif
Statistiques

문제 설명

$n$개의 정점으로 이루어진 방향 그래프가 있으며, 정점에는 $1$부터 $n$까지 번호가 매겨져 있습니다. 각 정점 $1 \le i \le n$에 대해, 정점 $i$의 진출 차수는 최대 1입니다. 따라서 이 그래프는 배열 $p_i$를 사용하여 나타낼 수 있는데, 정점 $i$의 진출 차수가 0이면 $p_i = 0$이고, 그렇지 않으면 $1 \le p_i \le n$, $p_i \ne i$이며 정점 $i$에서 정점 $p_i$로 가는 방향 간선이 존재합니다. 그래프에는 방향 사이클이 없으므로, 임의의 정점 $i$에서 출발하여 방향 간선을 따라 다음 정점으로 계속 이동하면 결국 진출 차수가 0인 정점에서 멈추게 됩니다.

처음에 정점 중 하나에 나무 체커(말)가 놓여 있습니다. 당신이 박수를 치면, 체커가 있는 정점 $i$의 $p_i$가 0이 아닐 때 체커는 정점 $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$번까지 할 수 있습니다.

추가하고 싶은 간선을 찾았다면, 추가할 방향 간선의 두 끝점 $1 \le x, y \le n$에 대해 $\texttt{! } x \text{ } y$ 형태의 한 줄을 출력하세요. 가능한 답이 여러 개라면 그중 아무것이나 출력해도 됩니다.

그러한 간선을 추가하는 것이 불가능하다면, 간선의 끝점 대신 $-1 \text{ -1}$을 출력하세요.

답을 출력한 직후 프로그램은 즉시 종료되어야 합니다.

각 질의를 출력한 후에는 출력 버퍼를 비워야(flush) 합니다.

인터랙터는 적응형(adaptive)이 아니며, 그래프는 사전에 고정되어 있습니다.

예제

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.