CF1617D2 Too Many Impostors (hard version)

这是一个交互题。简单版和困难版的唯一区别在于提问次数的限制。 有 $n$ 个玩家，编号从 $1$ 到 $n$。保证 $n$ 是 $3$ 的倍数。 其中有 $k$ 个“impostor”，其余 $n-k$ 个是“crewmate”。“impostor”的数量 $k$ 未知。保证 $\frac{n}{3} < k < \frac{2n}{3}$。 每次提问时，你可以选择三个不同的整数 $a$、$b$、$c$（$1 \le a, b, c \le n$），并询问：“在编号为 $a$、$b$、$c$ 的玩家中，impostor 的数量是否多于 crewmate？”如果 impostor 多于 crewmate，返回整数 $0$，否则返回 $1$。 你需要在最多 $n+6$ 次提问内，找出 impostor 的数量 $k$ 以及所有 impostor 的编号。 评测器是自适应的，也就是说 impostor 的编号可能不是预先固定的，可以根据你的提问动态决定。保证在任何时刻，你的所有提问结果都能对应至少一组满足条件的 impostor 分布。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$6 \le n < 10^4$，$n$ 是 $3$ 的倍数），表示玩家数量。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^4$。

对于每组测试数据，交互从读取 $n$ 开始。 然后你最多可以进行 $n+6$ 次提问，格式如下： `? a b c`（$1 \le a, b, c \le n$，且 $a$、$b$、$c$ 两两不同）。 每次提问后，你需要读取一个整数 $r$，如果在 $a$、$b$、$c$ 中 impostor 数量多于 crewmate，则 $r=0$，否则 $r=1$。 如果你收到 $-1$，说明你的提问不合法，请立即退出，否则会收到 Wrong answer 判定。否则你可以继续，因为你的程序会继续从关闭的流中读取数据。 当你确定所有 impostor 的编号后，输出一行： `! k x_1 x_2 \ldots x_k` 其中 $k$ 是 impostor 的数量，$x_1, x_2, \ldots, x_k$ 是所有 impostor 的编号。请注意，所有内容必须在同一行输出。 输出后，你的程序应继续解决剩余的测试数据，或在全部测试数据解决后退出。 每次输出后请记得换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。

示例交互说明（仅用于演示交互过程，不提供解题思路）： 对于第一组测试数据： 提问 `? 1 2 3` 返回 $0$，说明 $1$、$2$、$3$ 中 impostor 多于 crewmate。 提问 `? 3 4 5` 返回 $1$，说明 $3$、$4$、$5$ 中 crewmate 多于 impostor。 输出 `! 3 4 1 2`，表示找到了所有 impostor，数量为 $k=3$，编号为 $4$、$1$、$2$。 对于第二组测试数据： 提问 `? 7 1 9` 返回 $1$，说明 $7$、$1$、$9$ 中 crewmate 多于 impostor。 输出 `! 4 2 3 6 8`，表示找到了所有 impostor，数量为 $k=4$，编号为 $2$、$3$、$6$、$8$。 由 ChatGPT 4.1 翻译