CF2022D2 Asesino (Hard Version)

这是该问题的困难版本。在本版本中，你必须使用尽可能少的询问次数。只有在两个版本都被解决的情况下，你才能进行 Hack。 这是一个交互式问题。 在墨西哥国家 IOI 集训中，有一个传统游戏叫做“Asesino”，它类似于“Among Us”或“Mafia”。 今天，有 $n$ 名玩家（编号从 $1$ 到 $n$）将参与“Asesino”游戏，游戏中有以下三种角色： - 骑士（Knight）：骑士总是说真话。 - 恶棍（Knave）：恶棍总是说谎。 - 冒名顶替者（Impostor）：冒名顶替者表面上被所有人认为是骑士，实际上却是恶棍。 每个玩家都会被分配一个角色。游戏中恰好有一名冒名顶替者，但骑士和恶棍的人数可以为任意（可能为零）。 作为游戏主持人，你不小心忘记了每个人的角色，但你需要确定谁是冒名顶替者。 为了找出冒名顶替者，你可以提出一些问题。每次提问，你可以选择两个玩家 $i$ 和 $j$（$1 \leq i, j \leq n$，$i \neq j$），并询问玩家 $i$ 是否认为玩家 $j$ 是骑士。问题的回答规则如下表所示： | | 骑士（Knight） | 恶棍（Knave） | 冒名顶替者（Impostor） | |---------|:--------------:|:-------------:|:----------------------:| | 骑士 | 是 | 否 | 是 | | 恶棍 | 否 | 是 | 否 | | 冒名顶替者 | 否 | 是 | — | 表中第 $a$ 行第 $b$ 列的回答表示当 $i$ 的角色为 $a$，$j$ 的角色为 $b$ 时的回答。例如，第一行第三列的“是”表示当 $i$ 是骑士，$j$ 是冒名顶替者时的回答是“是”。 请用最少的询问次数找出冒名顶替者。也就是说，设 $f(n)$ 为对于 $n$ 个玩家，存在一种策略最多用 $f(n)$ 次询问就能确定冒名顶替者。你必须在不超过 $f(n)$ 次询问内确定冒名顶替者。 注意：评测器是自适应的：玩家的角色在一开始并未固定，可能会根据你的提问动态变化。但保证始终存在一种角色分配方式，使得所有已提问的问题都满足本题的约束。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 10^5$），表示参与游戏的人数。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

每次提问时，输出一行，格式如下： - "? i j"（$1 \leq i, j \leq n$，$i \neq j$）——表示询问玩家 $i$ 是否认为玩家 $j$ 是骑士。 评测器会返回 "1" 表示玩家 $i$ 认为玩家 $j$ 是骑士，返回 "0" 表示不是。 当你确定了冒名顶替者是谁时，输出一行，格式如下： - "! i"（$1 \leq i \leq n$）——表示第 $i$ 位玩家是冒名顶替者。 注意，输出答案不计入 $f(n)$ 次询问的限制。 如果你的输出不合法、询问次数超过 $f(n)$ 或者错误地确定了冒名顶替者，评测器会返回 "-1"，你的程序必须立即终止。否则，你的程序可能会因为读取已关闭的流而收到任意判题结果。 每次输出询问后，别忘了输出换行并刷新输出缓冲区。否则，你会因“Idleness limit exceeded”而被判为超时。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Python：sys.stdout.flush() - Rust：std::io::stdout().flush() - 其它语言请参见相关文档。 Hack 格式 对于 Hack，请使用如下格式。 第一行包含一个整数 $t$，表示测试用例数量。 每个测试用例的第一行包含整数 $n$ 和字符串 "manual"。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \leq a_i \leq 1$），表示每个玩家的角色。$1$ 表示骑士，$0$ 表示恶棍，$-1$ 表示冒名顶替者。必须恰好有一个 $a_i = -1$。 例如，Hack 输入格式如下： ``` 2 7 manual 0 1 0 -1 0 1 0 4 manual 0 1 -1 0 ```

注意，示例测试用例并不代表最优的提问策略，仅用于演示交互格式。实际上，通过示例中的提问无法确定冒名顶替者。 在第一个测试用例中，第 $2$ 和第 $6$ 位玩家是骑士，第 $1$、$3$、$5$、$7$ 位玩家是恶棍，第 $4$ 位玩家是冒名顶替者。以下是各次提问的解释： - 第一次提问，$i$ 是恶棍，$j$ 是恶棍。回答为“是”，因为恶棍总是说谎。 - 第二次提问，$i$ 是恶棍，$j$ 是骑士。回答为“否”，因为恶棍总是说谎。 - 第三次提问，$i$ 是骑士，$j$ 是恶棍。回答为“否”，因为骑士总是说真话。 - 第四次提问，$i$ 是骑士，$j$ 是骑士。回答为“是”，因为骑士总是说真话。 - 第五次提问，$i$ 是冒名顶替者，$j$ 是恶棍。回答为“是”，因为冒名顶替者总是说谎。 - 第六次提问，$i$ 是冒名顶替者，$j$ 是骑士。回答为“否”，因为冒名顶替者总是说谎。 - 第七次提问，$i$ 是恶棍，$j$ 是冒名顶替者。回答为“否”，因为恶棍总是说谎，并且恶棍认为冒名顶替者是骑士。 由 ChatGPT 4.1 翻译