← 返回题目列表

Codeforces · 2207/H3

H3. 库巴的城堡(困难版)

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

最终 Boss 第 2 阶段(熔岩)/ Giant Bowser — Shiho Fujii、Ryo Nagamatsu、新超级马里奥兄弟 Wii

这是问题的困难版本。版本之间的区别在于,在此版本中,$$$n \leq 400$$$ 并且您可以进行$$$1500$$$ 查询。只有解决了该问题的所有版本,您才能破解。

这是一个交互问题。

令 $$$n$$$ 为正整数。调用 $$$n$$$ 变量 $$$x_1, \ldots, x_n$$$ 上的函数 最小-最大 如果它可以被构造为仅写入 $$$\min$$$ 和 $$$\max$$$ 调用 $$$x_1, \ldots, x_n$$$ ,每个变量在表达式中按从左到右的顺序恰好出现一次。例如,$$$\min(x_1, x_2, x_3)$$$ 是 $$$3$$$ 变量上的最小-最大函数,但 $$$\max(\min(x_1, x_3), x_2)$$$ 和 $$$\min(\max(x_1, x_2), \max(x_2, x_3))$$$ 不是。

Bowser 在 $$$n$$$ ($$$2 \leq n \leq 400$$$) 变量上选择了最小-最大函数,并告诉您 $$$n$$$。此外,他还允许您提出以下形式的查询:您向 Bowser $$$n$$$ 整数 $$$x_1, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) 作为输入,他会告诉您 $$$f(x_1, \ldots, x_n)$$$。

要逃离他的城堡,你必须总共使用最多 $$$1500$$$ 查询来推断他的功能。之后,为了向他证明你已经学会了这个函数,Bowser 会给你最多 $$$5000$$$ 他自己的输入 $$$x_1, \ldots, x_n$$$,你必须用正确的值 $$$f(x_1, \ldots, x_n)$$$ 来响应。

由于Bowser的城堡非常安全,他实际上有多种功能供你弄清楚,总变量数最多为$$$400$$$。此外,他还限制您在所有函数中最多使用 $$$1500$$$ 查询,并且他总共不会提出超过 $$$5000$$$ 查询。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 400$$$) — min-max 函数中的变量数量。

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

阅读此行输入后,交互将从您的第一个查询开始。

互动

要进行查询,请按以下格式输出一行(不带引号):

  • "? $$$x_1$$$ $$$x_2$$$ $$$\ldots$$$ $$$x_n$$$" ($$$1 \leq x_i \leq 10^9$$$)。

然后,在每次查询后,读取一个整数——查询的答案。您最多可以进行 $$$1500$$$ 此类查询 所有 $$$t$$$ 测试用例的总计 。

一旦您准备好开始回答 Bowser 的查询,请输出包含单个字符的行“!“(不带引号)。

Bowser 的每个查询都包含一行 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) - Bowser 的输入。保证 Bowser 不会进行超过 $$$5000$$$ 查询 。

每次查询后,输出一个整数 - $$$f(x_1, x_2, \ldots, x_n)$$$ 的值。请注意,这些查询是 在线,因此 Bowser 只会在您回复上一个查询后才为您提供下一个查询。

Bowser 完成查询后,您将收到一行包含整数 $$$0$$$。之后,继续进行下一个测试用例,或者如果这是最后一个测试用例则退出。

此任务中的交互器是 部分自适应。特别是,Bowser 选择的功能在每次交互开始时都是固定的,但他向您提出的问题可能会发生变化。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,则您的解决方案必须立即退出。这意味着您的解决方案将获得 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客

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

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 200$$$) — 测试用例的数量。

每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 400$$$) — min-max 函数中的变量数量。

每个测试用例的第二行应包含以下列表中的一系列空格分隔的标记(不带引号),指定 min-max 函数:

  • "分钟"
  • "最大"
  • "("
  • ")"
  • ","
  • $$$1, 2, \ldots, n$$$ 范围内的正整数。

所有测试用例的 $$$n$$$ 总和不应超过 $$$400$$$。

例如,示例输入对应的黑客案例如下:

2
3
max ( 1 , 2 , 3 )
4
min ( max ( 1 , 2 ) , max ( 3 , 4 ) )

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

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

示例

输入
复制

2
3

5

2

3 6 2

3 5 7

0
4

8

3

8 7 6 5

0

输出
复制


? 5 4 3

? 1 2 1

!

6

7


? 1 9 8 7

? 5 1000000000 2 3

!

6

注意

在第一个测试用例中,Bowser 的最小-最大函数为 $$$f := \max(x_1, x_2, x_3)$$$。在提出两个查询以从评审团收到 $$$f(5, 4, 3) = 5$$$ 和 $$$f(1, 2, 1) = 2$$$ 后,解决方案就可以回答评审团的查询了。它正确推导出 $$$f(3, 6, 2) = 6$$$ 和 $$$f(3, 5, 7) = 7$$$。

在第二个测试用例中,Bowser 的最小-最大函数为 $$$f := \min(\max(x_1, x_2), \max(x_3, x_4))$$$。在提出两个查询以从评审团收到 $$$f(1, 9, 8, 7) = 8$$$ 和 $$$f(5, 10^9, 2, 3) = 3$$$ 后,该解决方案已准备好回答评审团的查询。它正确推导出 $$$f(8, 7, 6, 5) = 6$$$。

请注意,不保证示例中的查询唯一确定最小-最大函数。该示例仅用于演示查询如何工作。示例输入和输出中的空行只是为了更好的可读性;您不需要在解决方案中输出它们。