CF1491F Magnets

这是一个交互题。 Kochiya Sanae 正在玩磁铁。她发现有些磁铁已经失磁了，于是她很好奇想要找出来。 共有 $n$ 个磁铁，每个磁铁可能属于以下三种类型之一： - N - S - - ——这些磁铁是失磁的。 注意，你事先并不知道这些磁铁的类型。 你有一台可以测量磁铁之间作用力的机器，你最多可以使用这台机器 $n+\lfloor \log_2 n \rfloor$ 次。 你可以将一些磁铁放在机器的左侧，一些放在右侧，然后启动机器。显然，每个磁铁在一次查询中最多只能放在一侧（你不必把所有磁铁都放进去）。同一个磁铁可以在不同的查询中被多次使用。 然后机器会告诉你这些磁铁之间产生的作用力。具体来说，设 $n_1, s_1$ 分别为左侧的 N 型和 S 型磁铁数量，$n_2, s_2$ 分别为右侧的 N 型和 S 型磁铁数量。那么它们之间的作用力为 $n_1 n_2 + s_1 s_2 - n_1 s_2 - n_2 s_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$，若 $i \neq j$，则 $a_i \neq a_j$）——表示放在左侧的磁铁编号。 - 第三行输出 $r$ 个整数 $b_1, \dots, b_r$（$1 \leq b_i \leq n$，若 $i \neq j$，则 $b_i \neq b_j$）——表示放在右侧的磁铁编号。 - 同一个磁铁不能同时出现在一次查询的左右两侧。即应保证对于任意 $i, j$，都有 $a_i \neq b_j$。当然，你可以让部分磁铁在本次查询中不被使用。 每次输出查询后不要忘记输出换行并刷新输出缓冲区。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 之后，你需要读取一个整数 $F$——表示这些磁铁产生的作用力。 注意，如果你的查询不合法（如查询次数超限、机器损坏或参数非法），交互器会立即终止。在这种情况下，你的程序应立即终止以获得 Wrong Answer 判定，而不是其它任意判定。 当你确信已经找出了所有失磁磁铁时，使用以下格式报告答案： - "! k A"，其中 $k$ 表示你找到的失磁磁铁数量，$A$ 是一个包含 $k$ 个不同整数（$1$ 到 $n$ 之间）的数组，表示你找到的失磁磁铁的编号。$A$ 中元素顺序任意。 - 如果这是最后一个测试用例，输出后应立即终止程序；否则应立即进入下一个测试用例。 注意，交互器是非自适应的。磁铁的类型在交互开始前就已经确定，并不会随着你的查询而改变。

样例中的空行仅用于帮助你理解交互过程。你无需输出这些空行。 在样例中，磁铁的类型为 NN--。 首先，你将第 3 个磁铁放在左侧，第 4 个磁铁放在右侧。它们都是失磁的，因此没有产生作用力。 然后，你将第 1 个磁铁放在左侧，第 2 和第 3 个磁铁放在右侧。第 3 个磁铁是失磁的，其余两个是 N 型，因此产生的作用力为 $1$。 接下来的两次查询，作用力均为 $0$，因为右侧只有失磁磁铁。 这样我们就能确定第 3 和第 4 个磁铁是失磁的，所以应输出 "! 2 3 4" 并退出。 由 ChatGPT 4.1 翻译