CF1713D Tournament Countdown

这是一道交互题。 有一场由 $2^n$ 位选手组成的锦标赛。 这个锦标赛的规则如下：第 $1$ 位选手与第 $2$ 位选手竞争，第 $3$ 位选手与第 $4$ 位选手竞争……以此类推，比赛结束时会只剩下一位参赛选手，这位参赛选手就是胜利者。 你不知道比赛的结果，但你想通过询问评审团来得知最后谁赢了。 每次询问评审团，你需要给定两个正整数 $a$ 和 $b$，$a$ 和 $b$ 分别代指两位选手的编号。 若 $a$ 选手 比 $b$ 选手 赢的回合更多，评委团将报出数字 $1$；如果 $b$ 选手 比 $a$ 选手 赢的回合更多，评审团将报出数字 $2$；如果这两位选手赢的回合一样多，评审团会报出数字 $0$。 你要做的是在不超过 $\lceil \frac{1}{3} \cdot 2^{n+1} \rceil$ 的次数内找到最后胜利的选手。此处 $\lceil x \rceil$ 表示四舍五入 $x$ 到最近的整数。 这场锦标赛已经过去很久了。所以保证有唯一解。

输入第一行是一个正整数 $t\ (1\leq t\leq 2^{14})$，表示测试组数。 第二行是一个正整数 $n\ (1\leq n\leq 17)$，作用如题目所述。 接下来若干行都是一个正整数，表示询问的结果。 保证所有测试用例之和不超过 $2^{17}$。

读取到 $n$ 后即开始询问。 要进行查询，请输出 " $?\ a\ b$ " $ (1\leq a, b\leq 2^n)$ 不包括引号。 若读入到了 $-1$ 或非有效值，这意味着程序在之前或现在**给出了无效的询问，或者是给出了错误的答案，或者是超出了查询的限制**。此时应停止程序。 若已经确定答案，且要给出答案，请输出 " $!\ x$ " $(1\leq x\leq 2^n)$ 不包括引号，且 $x$ 表示当前判断的最后的赢家。给出答案的次数无限制，即，给出答案不会计入到已询问的次数中。 注意，在每次**回答完成当前数据组或回答完成全部数据组**，程序都应该立即跳出，并刷新缓存区（~~不然呢？ILE大礼包警告~~），你可以： - 在 `C++`，使用 `fflush(stdout)` 或 `cout.flush()` 或 `cout

The tournament in the first test case is shown below. The number of wins is $ [1,0,0,2,0,1,3,0] $ . In this example, the winner is the $ 7 $ -th contestant.