CF1438F Olha and Igor

这是一个交互题。 Igor 想要找到通往 Olha 心灵的钥匙。问题在于，这把钥匙藏在一棵二叉树的根节点上。 有一棵高度为 $h$ 的完美二叉树，共有 $n = 2^{h} - 1$ 个节点。每个节点都被分配了 $1$ 到 $n$ 的不同标签。然而，Igor 只知道 $h$，并不知道每个标签对应哪个节点。 为了找到通往 Olha 心灵的钥匙，他需要在最多 $n+420$ 次的查询中，找出根节点的标签。每次查询可以进行如下操作： - 选择三个不同的标签 $u$、$v$ 和 $w$（$1 \leq u,v,w \leq n$）。 - 作为回应，Olha（评测器）会告诉他：如果以标签为 $w$ 的节点作为根节点，那么标签为 $u$ 和 $v$ 的节点的最近公共祖先的标签。 请你帮助 Igor 找到根节点的标签！ 注意：评测器是非自适应的，所有标签在所有查询前就已经固定。

第一行包含一个整数 $h$（$3 \le h \le 18$），表示二叉树的高度。

你需要首先读取 $h$。 每次查询标签 $u, v, w$ 时，在单独一行输出 "? u v w"。 查询中的数字需满足 $1 \le u, v, w \le n$，且 $u \ne v$，$u \ne w$，$v \ne w$。 作为回应，你会收到 $1 \le x \le n$，表示如果以 $w$ 为根节点，$u$ 和 $v$ 的最近公共祖先的标签。 如果你的查询无效，或者查询次数超过 $n+420$，程序会输出 $-1$ 并终止交互。你会收到 Wrong answer 判定。请立即退出以避免其他判定。 当你确定根节点的标签后，输出 "! r"，其中 $r$ 是根节点的标签。 每次输出查询后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请参考相关文档。 Hack 格式 Hack 时请使用以下格式： 第一行输入一个整数 $h$（二叉树高度）。 第二行输出一个长度为 $n = 2^h - 1$ 的排列 $p$。这表示一棵二叉树，根节点标签为 $p_1$，对于 $1 < i \le n$，$p_i$ 的父节点为 $p_{ \lfloor{\frac{i}{2}}\rfloor }$。

示例中的标签排列为 $[4, 7, 2, 6, 1, 5, 3]$，即根节点标签为 $4$，对于 $1 < i \le n$，$p_i$ 的父节点为 $p_{ \lfloor{\frac{i}{2}}\rfloor }$。 由 ChatGPT 4.1 翻译