← 返回题目列表

Codeforces · 2129/F2

F2. Top-K 追踪器(困难版)

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

这是一个交互问题。

这是问题的困难版本。唯一的区别是这个版本中的 $$$n \le 890$$$ 。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

有一个隐藏的排列 $$$p$$$,它是 $$$\{1,2,\ldots,n\}$$$ 的排列。设$$$pos_i$$$表示值$$$i$$$在$$$p$$$中的位置,即$$$pos_{p_i} = i$$$。

要找到此排列,您可以提出四种类型的查询:

  • "$$$1\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$、$$$i_1、\ i_2、\ \ldots、\ i_m$$$ 必须不同)。令 $$$k = \min(60, m)$$$。评审团将按升序返回 $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ 中最高的 $$$k$$$ 最大数字。
  • "$$$2\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$、$$$i_1、\ i_2、\ \ldots、\ i_m$$$ 必须不同)。令 $$$k = \min(60, m)$$$。评审团将按升序返回 $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ 中最高的 $$$k$$$ 最大数字。

  • "$$$3\ m\ i_1\ i_2\ ...\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ ...,\ i_m$$$ 必须不同)。让 $$$k = \min(300, m)$$$。评审团将按升序返回 $$$[p_{i_1}, p_{i_2}, ..., p_{i_m}]$$$ 中最高的 $$$k$$$ 最大数字。
  • "$$$4\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$、$$$i_1、\ i_2、\ \ldots、\ i_m$$$ 必须不同)。让 $$$k = \min(300, m)$$$。评审团将按升序返回 $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ 中最高的 $$$k$$$ 最大数字。

令 $$$c_i$$$ 为 $$$i$$$ $$$(1 \le i \le 4)$$$ 类型的查询的使用计数。您的查询计数必须满足以下限制:

  • $$$c_1+c_2+c_3+c_4 \le 30.$$$
  • $$$c_3+c_4 \le 1.$$$

输入

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

互动

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 890$$$)。此时,选择排列$$$p$$$。此任务中的交互器是 不自适应。换句话说,排列 $$$p$$$ 在每个测试用例中都是固定的,并且在交互过程中不会改变。

要询问 $$$1$$$ 类型的查询,您需要打印以下形式的行(不带引号):

  • "$$$1\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ 必须不同)

之后,您将收到 $$$k=\min(60,m)$$$ 整数 — $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ 中按升序排列的顶部 $$$k$$$ 最大数字。

要询问 $$$2$$$ 类型的查询,您需要打印以下形式的行(不带引号):

  • "$$$2\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$、$$$i_1、i_2、\ldots、i_m$$$ 必须不同)

之后,您将收到 $$$k=\min(60,m)$$$ 整数 — $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ 中按升序排列的最高 $$$k$$$ 最大数字。

要询问 $$$3$$$ 类型的查询,您需要打印以下形式的行(不带引号):

  • "$$$3\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$、$$$i_1、i_2、\ldots、i_m$$$ 必须不同)

之后,您将收到 $$$k=\min(300,m)$$$ 整数 — $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ 中按升序排列的顶部 $$$k$$$ 最大数字。

要询问 $$$4$$$ 类型的查询,您需要打印以下形式的行(不带引号):

  • "$$$4\ m\ i_1\ i_2\ \ldots\ i_m$$$" ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ 必须不同)

之后,您将收到 $$$k=\min(300,m)$$$ 整数 — $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ 中按升序排列的最高 $$$k$$$ 最大数字。

接下来,如果您的程序找到了排列 $$$p$$$,请打印以下形式的行(不带引号):

  • “$$$!\ p_1\ p_2\ \ldots\ p_n$$$”

请注意,这一行是 不 被认为是一个查询,并且是 不 在计算询问的数量时考虑在内。

此后,继续下一个测试用例。

打印测试用例的查询或答案后,不要忘记输出行尾并刷新输出。否则,你将得到判决 超出空闲限制。为此,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • System.out.flush() 在 Java 中;
  • 冲洗(输出) 帕斯卡;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

要破解,请遵循以下测试格式。

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 890$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$,这是 $$$\{1,2,\ldots,n\}$$$ 的排列。

示例

输入
复制

2
3

2 3

3

2

2



输出
复制


3 2 3 1

2 1 2

! 3 1 2

4 1 1

! 2 1

注意

在第一个测试用例中,隐藏排列是 $$$p = [3, 1, 2]$$$。因此,$$$pos = [2, 3, 1]$$$。

对于查询“3 2 3 1”,陪审团返回 $$$2$$$ 和 $$$3$$$,因为 $$$2$$$ 和 $$$3$$$ 是 $$$[p_3, p_1]$$$ 中最高的 $$$k$$$ 最大数字,其中 $$$k = \min(300, m) = \min(300, 2) = 2$$$。

对于查询“2 1 2”,陪审团返回 $$$3$$$,因为 $$$3$$$ 是 $$$[pos_2]$$$ 中最高的 $$$k$$$ 最大数字,其中 $$$k = \min(60, m) = \min(60, 1) = 1$$$。

请注意,该示例仅用于理解该语句,并且不 不 保证找到唯一的排列$$$p$$$。