这是一个交互问题。
Kochiya Sanae 正在玩磁铁。她意识到其中一些磁铁已经消磁,因此很想找出它们。
有 $$$n$$$ 磁铁,可以是以下 $$$3$$$ 类型:
- N
- S
- - — 这些磁铁已消磁。
请注意,您事先并不知道这些磁铁的类型。
你有一台可以测量磁铁之间的力的机器,你最多可以使用它 $$$n+\lfloor \log_2n\rfloor$$$ 次。
您可以在机器的左侧放置一些磁铁,在机器的右侧放置一些磁铁,然后启动机器。显然,您最多可以将一块磁铁放在一侧(不必放置所有磁铁)。您可以在不同的查询中放置相同的磁铁。
然后机器会告诉你这些磁铁产生的力。正式地,令 $$$n_1,s_1$$$ 为左侧 N 和 S 磁体的数量,$$$n_2,s_2$$$ 为右侧的 N 和 S 磁体数量。那么它们之间的力就是$$$n_1n_2+s_1s_2-n_1s_2-n_2s_1$$$。请注意,力是一个带符号的值。
然而,当力的绝对值严格大于$$$n$$$时,机器就会崩溃。
你需要找到所有类型为 - 的磁铁(所有消磁的磁铁),而不破坏机器。
请注意,交互器不具有自适应性。磁铁的类型在交互开始之前是固定的,并且不会随着查询而改变。
保证至少有 $$$2$$$ 类型非 - 的磁铁,以及至少 $$$1$$$ 类型 - 的磁铁。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
互动
对于每个测试用例,您应该首先读取一个整数 $$$n$$$ ($$$3 \leq n \leq 2000$$$) — 磁铁的数量。
保证所有测试用例的$$$n$$$ 总和不超过$$$2000$$$。
之后,您可以将一些磁铁放入机器中并从语句中进行查询。
您必须分三行打印每个查询:
- 在第一行中打印“? l r”(不带引号),其中 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l,r < n$$$, $$$l+r \leq n$$$) 分别表示您放置在左侧和右侧的磁铁的数量。
- 在第二行中打印 $$$l$$$ 整数 $$$a_1, \dots, a_l$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$) — 放置在左侧的磁铁的索引。
- 在第三行中打印 $$$r$$$ 整数 $$$b_1, \dots, b_r$$$ ($$$1 \leq b_i \leq n$$$, $$$b_i \neq b_j$$$ if $$$i \neq j$$$) — 您放置在右侧的磁铁的索引。
- 同一个磁铁不能放置在同一查询的两侧。形式上,您应该保证对于任何 $$$i$$$ 和 $$$j$$$ 都有 $$$a_i \neq b_j$$$ 。但是,您可以保留一些未使用的磁铁。
打印查询后,不要忘记输出行尾并刷新输出。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
在此之后,您应该读取一个整数 $$$F$$$ — 这些磁铁产生的力。
请注意,如果您的查询无效(超出查询限制、机器崩溃或参数无效),交互器将立即终止。在这种情况下,终止您的程序以接收错误答案的判决而不是任意判决。
如果您对自己的答案有信心,请使用以下格式进行报告:
- “!k A”,其中 $$$k$$$ 是您找到的磁铁数量,$$$A$$$ 是一个由 $$$k$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 表示您找到的磁铁类型的索引。您可以按任意顺序打印 $$$A$$$ 的元素。
- 之后,如果这是最后一个测试用例,则必须终止程序;否则你应该立即继续处理下一个测试用例。
请注意,交互器不具有自适应性。磁铁的类型在交互开始之前是固定的,并且不会随着查询而改变。
黑客
要破解解决方案,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 你的 hack 中测试用例的数量。
然后按照 $$$t$$$ 测试用例的描述进行操作,每个测试用例打印两行:
- 第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2000$$$) — 磁铁的数量。
- 第二行包含长度为 $$$n$$$ 的字符串 $$$S$$$,仅由 N、S 和 - 组成,表示磁铁的类型。
- 每个测试用例应保证至少有 $$$2$$$ 类型不是 - 的磁铁,并且至少有 $$$1$$$ 类型 - 的磁铁。同时,所有测试用例中$$$n$$$的总和不应超过$$$2000$$$。
示例
输入 #1
1 4 0 1 0 0
输出 #1
? 1 1 3 4 ? 1 2 1 2 3 ? 1 1 1 4 ? 1 1 1 3 ! 2 3 4
注意
示例中的空行只是为了让您更好地理解交互过程。您不需要打印它们。
样本中,磁铁的类型为NN--。
首先,将第三个磁铁放在左侧,第四个磁铁放在右侧。它们的类型都是 -,因此不会产生力。
然后将第一个磁铁放在左侧,第二个和第三个磁铁放在右侧。第三个磁铁的类型为 -,而另外两个磁铁的类型为 N,因此产生的力为 $$$1$$$。
在以下两个查询中,力为 $$$0$$$,因为只有一块具有属性 - 的磁铁位于右侧。
然后我们可以确定类型 - 的磁铁是第三个和第四个,所以我们应该打印! 2 3 4 然后退出。