这是一个交互问题。
这是问题的简单版本。唯一的区别是这个版本中的 $$$n \le 845$$$ 。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
有一个隐藏的排列 $$$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 845$$$)。此时,选择排列$$$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++ 中; Java 中的
- System.out.flush() ;
- 冲洗(输出) 帕斯卡;
- stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
黑客
要破解,请遵循以下测试格式。
第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 40$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 845$$$)。
每个测试用例的第二行包含 $$$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$$$。