← 返回题目列表

Codeforces · 2152/E

E. 单调子序列

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

这是一个交互问题。

Faker又调皮了。您要求他创建一个很好的查询问题,但他创建了一个交互式问题,而他正在回答查询! Faker向你隐藏了一个排列,你必须通过与他互动来推断出一些有趣的信息。

给你一个整数$$$n$$$。 Faker 隐藏了长度为 $$$n^2+1$$$ 的隐藏排列$$$^{\text{*}}$$$ $$$p_1, p_2, \ldots, p_{n^2+1}$$$。您的目标是找到隐藏排列的单调子序列(递增或递减),长度恰好为 $$$n+1$$$。可以证明,每个长度为$$$n^2 + 1$$$的排列都包含一个长度为$$$n+1$$$的单调子序列。有关证明的更多信息,您可以查看此维基百科页面。

要找到它,你最多可以赚 $$$n$$$ 摩天大楼查询 到交互器,其定义如下:

  • 您提供一组 $$$k$$$ 索引作为严格递增序列:$$$i_1, i_2, \ldots, i_k$$$。
  • 交互器考虑这些索引处隐藏排列的值:$$$p_{i_1}、p_{i_2}、\ldots、p_{i_k}$$$。
  • 然后交互器返回对应于 可见的摩天大楼 来自此集合。如果索引 $$$i_j$$$ 的值 $$$p_{i_j}$$$ 大于查询中所有前面元素的值,即 $$$p_{i_j} \gt p_{i_m}$$$ 对于所有 $$$1 \le m \lt j$$$,则索引 $$$i_j$$$ 可见。这相当于查找序列 $$$(p_{i_1}, \ldots, p_{i_k})$$$ 的从左到右最大值的索引。

在进行最多 $$$n$$$ 查询后,您必须报告长度为有效的单调子序列 正是 $$$n+1$$$。

请注意,排列 $$$p$$$ 是固定的 之前 进行任何查询并且不依赖于查询。

$$$^{\text{*}}$$$长度$$$m$$$的排列是一个由从$$$1$$$到$$$m$$$以任意顺序的$$$m$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$m=3$$$但数组中有$$$4$$$)。

输入

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

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。

保证所有测试用例的$$$n^2+1$$$总和不超过$$$10\,001$$$。

互动

每个测试用例的交互从读取整数 $$$n$$$ 开始。

要进行查询,请按以下格式打印一行:

  • ? $$$k \; i_1 \; i_2 \; \l点\;我_k$$$
其中 $$$k$$$ 是查询中的索引数量 ($$$1 \le k \le n^2+1$$$),$$$i_1, \ldots, i_k$$$ 是索引本身,满足 $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n^2+1$$$。 索引应按排序顺序显示。

作为响应,交互器将以以下格式打印一行:

  • $$$c \; j_1 \; j_2 \; \l点\; j_c$$$

其中 $$$c$$$ 是查询中可见摩天大楼的数量 ($$$1 \le c \le k$$$),$$$j_1, \ldots, j_c$$$ 是它们的索引,满足 $$$1 \le j_1 \lt j_2 \lt \ldots \lt j_c \le n^2+1$$$。索引将按排序顺序呈现。

要报告您的最终答案,请按以下格式打印一行:

  • ! $$$s_1 \; s_2 \; \l点\; s_{n+1}$$$
其中 $$$s_1, \ldots, s_{n+1}$$$ 是形成长度为 $$$n+1$$$ 的单调子序列的元素的索引,满足 $$$1 \le s_1 \lt s_2 \lt \ldots \lt s_{n+1} \le n^2 + 1$$$。 索引应按排序顺序显示。

请注意回答 不算数 朝着你的命令限制。

打印答案后,您的程序应继续执行下一个测试用例,如果没有更多测试用例,则终止。

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

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

黑客

要破解,请使用以下格式。

第一行应包含单个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$)。

每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$)。

每个测试用例的第二行应包含 $$$n^2+1$$$ 空格分隔的整数 $$$p_1,p_2,\ldots,p_{n^2+1}$$$ ($$$1 \leq p_i \leq n^2+1$$$)。 $$$p$$$ 应该是长度 $$$n^2+1$$$ 的排列。

$$$n^2+1$$$ 的总和不应超过 $$$10\,001$$$。

例如,以下是示例测试的 hack 格式:

2
1
1 2
2
5 3 4 1 2

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

2
1

2 1 2

2

1 1

2 2 3

输出
复制


? 2 1 2

! 1 2

? 3 1 2 3

? 3 2 3 5

! 1 3 4

注意

对于第一个测试用例,$$$n=1$$$。隐藏的排列是 $$$p=[1, 2]$$$。

  • 查询 ? 2 1 2,可见的摩天大楼位于索引 $$$1$$$ 和 $$$2$$$ 处。交互器返回 2 1 2.
  • 报告索引 $$$1、2$$$ 处长度为 $$$2$$$ 的递增子序列。

对于第二个测试用例,$$$n=2$$$。隐藏排列是 $$$p=[5, 3, 4, 1, 2]$$$。

  • 查询 ? 3 1 2 3,可见的摩天大楼位于索引 $$$1$$$ 处。交互器返回 1 1.
  • 查询 ? 3 2 3 5,可见的摩天大楼位于索引 $$$2$$$ 和 $$$3$$$ 处。交互器返回 2 2 3.
  • 报告索引 $$$1, 3, 4$$$ 处长度 $$$3$$$ 的递减子序列。

虽然Faker会扮演互动者的角色,但互动者永远不会骗你。