← 返回题目列表

Codeforces · 1918/E

E. ace5 和任务顺序

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

这是一个交互问题!

在新一轮中,有$$$n$$$个任务,难度从$$$1$$$到$$$n$$$。协调员决定以未排序的难度顺序进行第一轮任务,并重新安排了任务,导致难度从 $$$1$$$ 排列为 $$$n$$$。之后,协调员通过以下方式挑战 ace5 猜测排列。

最初,协调器从 $$$1$$$ 到 $$$n$$$ 中选择一个数字 $$$x$$$。

ace5 可以进行以下形式的查询:$$$?\ i$$$。答案将是:

- $$$>$$$,如果 $$$a_i > x$$$,则 $$$x$$$ 增加 $$$1$$$。
- $$$<$$$,如果 $$$a_i < x$$$,则 $$$x$$$ 减少 $$$1$$$。
- $$$=$$$,如果 $$$a_i = x$$$,则 $$$x$$$ 保持不变。

ace5 的任务是在不超过 $$$40n$$$ 查询中猜测排列。由于ace5太忙,所以他把这个任务交给了你。

输入

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

互动

你的程序和陪审团程序之间的交互从读取正整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) 开始——隐藏排列的长度。

要进行查询,请以“? i”格式输出一行,其中 $$$1 \leq i \leq n$$$。

作为答复,您将收到:

- ">",如果 $$$a_i$$$ > $$$x$$$,则 $$$x$$$ 将增加 $$$1$$$。
- “<”,如果 $$$a_i$$$ < $$$x$$$,则 $$$x$$$ 将减少 $$$1$$$。
- “=”,如果 $$$a_i$$$ = $$$x$$$,则 $$$x$$$ 将保持不变。

您最多可以进行 $$$40n$$$ 查询。要输出答案,需要打印“!a_1 a_2 ... a_n”,其中$$$1 \leq a_i \leq n$$$,并且它们都是不同的。输出答案不算作查询。

如果您的程序对一个测试用例进行超过 $$$40n$$$ 查询,或者进行无效查询,则对该查询的响应将为 -1。收到这样的响应后,您的程序应立即终止以接收“错误答案”的判决。否则,它可能会收到任何其他判决。

输出查询后,不要忘记打印换行符并刷新输出缓冲区。否则,您将收到“演示错误”的判决。要刷新缓冲区,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

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

此问题中的交互器不具有自适应性。

黑客:

要进行破解,请使用以下格式:

第一行包含一个整数 $$$t$$$ — 测试用例的数量。

每个测试用例的描述应由两行组成。第一行包含数字 $$$n$$$ 和 $$$x$$$ ($$$1 \leq x \leq n \leq 2000$$$) — 隐藏排列的长度和数字 $$$x$$$ 的初始值。第二行包含 $$$n$$$ 不同的数字 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 陪审团在此测试用例中应选择的排列。

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

示例

输入 #1

2
5

>

=

<

=

<

<

2

>

输出 #1

? 4

? 2

? 1

? 5

? 1

? 3

! 2 4 1 5 3

? 1

! 2 1

注意

在第一个测试中,隐藏排列为 $$$a$$$ = [$$$2,4,1,5,3$$$],$$$x$$$ 的初始值为 $$$3$$$。

在第二个测试中,隐藏排列为 $$$a$$$ = [$$$2,1$$$],$$$x$$$ 的初始值为 $$$1$$$。