← 返回题目列表

Codeforces · 1815/B

B. 总和图

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

这是一个交互问题。

有一个隐藏的排列 $$$p_1, p_2, \dots, p_n$$$。

考虑一个无向图,其中只有 $$$n$$$ 个节点,没有边。您可以进行两种类型的查询:

1. 指定一个整数$$$x$$$,满足$$$2 \le x \le 2n$$$。对于所有整数 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$1 \le x-i \le n$$$,将在节点 $$$i$$$ 和节点 $$$x-i$$$ 之间添加一条边。
2、查询节点$$$p_i$$$到节点$$$p_j$$$之间最短路径的边数。作为这个问题的答案,如果存在这样的路径,您将获得最短路径中的边数;如果不存在这样的路径,您将获得 $$$-1$$$ 。

请注意,您可以按任意顺序进行这两种类型的查询。

在 $$$2n$$$ 查询中(包括类型 $$$1$$$ 和类型 $$$2$$$),猜测两种可能的排列,其中至少一种是 $$$p_1, p_2, \dots, p_n$$$。如果至少其中一种排列是正确的,您就会被接受。您可以猜测相同的排列两次。

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

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^3$$$) — 排列的长度。

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

互动

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

然后,最多进行 $$$2n$$$ 查询:

- 如果要进行类型 $$$1$$$ 查询,请输出“+ x”。 $$$x$$$ 必须是 $$$2$$$ 和 $$$2n$$$(含)之间的整数。完成后读取 $$$1$$$ 或 $$$-2$$$。如果您读取$$$1$$$,您的查询是有效的,否则它是无效的,或者您超出了查询限制,并且您的程序必须立即终止以接收错误答案判决。
- 如果要进行类型 $$$2$$$ 查询,请输出“? i j”。 $$$i$$$ 和 $$$j$$$ 必须是 $$$1$$$ 和 $$$n$$$ 之间的整数(含)。之后,读入一个整数 $$$r$$$ ($$$-1 \le r \le n$$$) — 您的查询的答案。如果您收到整数 $$$−2$$$ 而不是答案,则意味着您的程序进行了无效查询,或者超出了查询限制。您的程序必须立即终止才能收到错误答案判决。

在交互的任何一点,如果你想猜测两个排列,请输出 "! $$$p_{1,1}$$$ $$$p_{1,2}$$$ $$$\dots$$$ $$$p_{1,n}$$$ $$$p_{2,1}$$$ $$$p_{2,2}$$$ $$$\dots$$$ $$$p_{2,n}$$$"。请注意,您应该在同一行输出两个排列,并且不需要感叹号来分隔两个排列。完成后读取 $$$1$$$ 或 $$$-2$$$。如果您读到$$$1$$$,您的答案是正确的,否则它是不正确的,您的程序必须立即终止才能收到错误答案的判决。之后,继续进行下一个测试用例,如果没有则终止程序。请注意,报告答案不算作查询。

请注意,即使输出正确的排列,第二个排列也应该是排列而不是任意数组。

在任何时候,如果您在读取整数 $$$-2$$$ 后继续交互,您可以获得任意结论,因为您的解决方案将继续从关闭的流中读取。

打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

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

交互器是非自适应的。这意味着所有排列在交互开始之前都是固定的。

黑客

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

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

每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \le n \le 10^3$$$) — 排列的长度。

每个测试用例的第二行应包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 隐藏排列。

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

示例

输入 #1

2
6

1

1

1

1

1

2

-1

1
2

1

输出 #1

+ 12

+ 2

+ 3

? 1 3

+ 5

? 1 5

? 4 5

! 1 4 2 5 3 6 1 2 3 4 5 6


! 1 2 2 1

注意

在第一个测试用例中,$$$n=6$$$ 和隐藏排列 $$$p = [1,4,2,5,3,6]$$$。

首先,分别对 $$$x=12, 2, 3$$$ 进行类型 $$$1$$$ 查询。这总共向图中添加了四个边:

- 连接节点 $$$6$$$ 和节点 $$$6$$$ 的边。
- 连接节点 $$$1$$$ 和节点 $$$1$$$ 的边。
- 连接节点 $$$1$$$ 和节点 $$$2$$$ 的边。
- 连接节点 $$$2$$$ 和节点 $$$1$$$ 的边。

由于所有这些查询都是有效的,因此交互器在每个查询之后返回 $$$1$$$。

然后,查询节点$$$p_1 = 1$$$和$$$p_3 = 2$$$之间最短路径的边数,等于$$$1$$$。

然后,对 $$$x=5$$$ 进行类型 $$$1$$$ 查询。这总共向图中添加了四个边:

- 连接节点 $$$1$$$ 和节点 $$$4$$$ 的边。
- 连接节点 $$$2$$$ 和节点 $$$3$$$ 的边。
- 连接节点 $$$3$$$ 和节点 $$$2$$$ 的边。
- 连接节点 $$$4$$$ 和节点 $$$1$$$ 的边。

由于此查询有效,因此交互器返回 $$$1$$$。

然后查询节点$$$p_1 = 1$$$到$$$p_5 = 3$$$之间的最短路径的边数,等于$$$2$$$。

然后,查询节点$$$p_4 = 5$$$和$$$p_5 = 3$$$之间的最短路径的边数。这样的路径不存在,因此交互器返回$$$-1$$$。

之后,由于某种魔法,确定了 $$$p$$$ 的两个可能的排列:第一个排列是 $$$[1,4,2,5,3,6]$$$,第二个排列是 $$$[1,2,3,4,5,6]$$$。由于第一个排列等于隐藏排列,因此该测试用例已正确解决。总共使用了 $$$7$$$ 查询,这在 $$$2 \cdot 6 = 12$$$ 查询的限制之内。

由于答案是正确的,交互器返回 $$$1$$$。

在第二个测试用例中,$$$n=2$$$,隐藏排列为$$$p = [2,1]$$$。

因为只有 $$$2! = 2$$$ 可能的排列,无需查询。只需输出两个排列 $$$[1,2]$$$ 和 $$$[2,1]$$$ 就足够了。总共使用了 $$$0$$$ 查询,这在 $$$2 \cdot 2 = 4$$$ 查询的限制之内。

由于答案是正确的,交互器返回 $$$1$$$。