← 返回题目列表

Codeforces · 2061/G

G. 凯文和团队

中文机器翻译题面 查看原题

这是一个交互问题。

Kevin 有 $$$n$$$ 同学,编号为 $$$1、2、\ldots、n$$$。他们中的任何两个人都可以是朋友,也可以不是朋友。

Kevin想要选择$$$2k$$$同学组成$$$k$$$个团队,每个团队恰好包含$$$2$$$人。每个人最多可以属于一个团队。

设 $$$u_i$$$ 和 $$$v_i$$$ 为第 $$$i$$$ 团队中的两个人。为了避免组队过程中潜在的冲突,团队成员必须满足以下两个条件之一:

- 对于所有 $$$i$$$ ($$$1\leq i \leq k$$$),同学 $$$u_i$$$ 和 $$$v_i$$$ 都是朋友。
- 对于所有 $$$i$$$ ($$$1\leq i \leq k$$$),同学 $$$u_i$$$ 和 $$$v_i$$$ 都不是朋友。

Kevin 想要确定最大 $$$k$$$,这样,无论 $$$n$$$ 人之间的友谊关系如何,他总能找到 $$$2k$$$ 人组成团队。之后,他需要组建 $$$k$$$ 团队。但是询问两个同学是否是朋友是很尴尬的,因此 Kevin 希望在询问不超过 $$$n$$$ 对同学的友谊状态时实现这一点。

交互器是自适应的。意味着同学之间的隐藏关系在交互之前并不是固定的,在交互过程中会发生变化。

互动

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$2\leq n \leq 10^5$$$) – 同学的数量。

首先,您应该输出一个整数 $$$k$$$ ($$$1\leq k\leq \frac{n}2$$$) — 您可以组建的最大团队数量。

您可以通过以下方式进行查询 - 打印 $$$?\;u\;v$$$ 形式的一行,其中 $$$1\leq u\neq v \leq n$$$。之后,读取一个整数:$$$0$$$ 或 $$$1$$$ 表示他们是否是朋友。 $$$1$$$ 表示他们是朋友,而 $$$0$$$ 表示不是朋友。

如果要打印答案,请输出 $$$!\;u_1\;v_1\;u_2\;v_2\;\ldots\;u_k\;v_k$$$。您应该准确输出 $$$2k$$$ 不同的数字。然后,继续与下一个测试用例进行交互。

您最多可以进行 $$$n$$$ 查询。打印答案不计入查询次数。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,您将得到超出空闲限制的判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将由于无效查询或任何其他错误而收到错误答案。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客

hacks 的交互器不具有自适应性。要进行破解,请使用以下格式。

第一行包含单词“manual”。

第二行包含一个整数 $$$t$$$ ($$$1\leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n \leq 10^5$$$) — 同学的数量。

每个测试用例的第二行包含一个由'0'和'1'组成的字符串$$$s$$$,长度为$$$\frac{n(n - 1)}{2}$$$ —表示$$$(1, 2)$$$、$$$(1, 3)$$$、$$$\ldots$$$、$$$(1, n)$$$、 $$$(2, 3)$$$、$$$(2, 4)$$$、$$$\ldots$$$、$$$(2, n)$$$、$$$\ldots$$$、$$$(n - 1, n)$$$。 “1”表示是朋友,“0”表示不是朋友。

以下是示例的输入。

所有测试用例的 $$$n$$$ 总和不得超过 $$$10^5$$$。

对于黑客攻击还有一个额外的限制:所有测试用例的 $$$\frac{n(n-1)}{2}$$$ 总和不得超过 $$$10^7$$$。

示例

输入 #1

2
3


1

5


1

0

1

0

0

输出 #1

1
? 1 2

! 1 2

2
? 1 2

? 3 4

? 3 5

? 1 3

? 2 4

! 1 2 3 5

注意

在第一个测试用例中:

Kevin 声称他可以组建 $$$1$$$ 团队,无论 $$$3$$$ 人之间的友谊关系如何。

Kevin 询问 $$$1$$$ 和 $$$2$$$ 之间的友谊关系。陪审团回应说他们是朋友。

Kevin 回答说他可以与 $$$1$$$ 和 $$$2$$$ 组成一个团队。

在第二个测试用例中:

Kevin 声称他可以组建 $$$2$$$ 团队,无论 $$$5$$$ 人之间的友谊关系如何。

Kevin 询问 $$$(1, 2), (3, 4), (3, 5), (1, 3), (2, 4)$$$ 之间的友谊关系。陪审团的回应为 $$$1, 0, 1, 0, 0$$$。

Kevin 回答说他可以与 $$$(1, 2)$$$ 和 $$$(3, 5)$$$ 组成两个团队。

也可以与 $$$(1, 3)$$$ 和 $$$(2, 4)$$$ 组成两个团队,因为他们都不是朋友。