Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Interactivo
Estadísticas

题目描述

给定一个包含 $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$ 非零,它就会移动到顶点 $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}$ 来代替边的两个端点。

输出答案后,你的程序必须立即终止。

每次发起查询后,请刷新输出缓冲区。

交互器是非自适应的;图在交互开始前就已经固定。

样例

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.