CF1498E Two Houses

这是一个交互题。在与测试程序通信时，请记得刷新输出。你可以在 C++ 中使用 fflush(stdout)，在 Java 中使用 system.out.flush()，在 Python 中使用 stdout.flush()，在 Pascal 中使用 flush(output) 来刷新输出。如果你使用其他编程语言，请查阅相关文档。你也可以参考关于交互题的指南：。 Dixit 住在一个城市里。这个城市有 $n$ 个房子。每一对房子之间恰好有一条有向道路。例如，考虑两个房子 A 和 B，要么有一条从 A 到 B 的有向道路，要么有一条从 B 到 A 的有向道路，但不会同时存在两条。第 $i$ 个房子的入度为 $k_i$。 如果房子 A 和房子 B 互相可达（即 A 可以到达 B，且 B 也可以到达 A），则称它们是“互达”的。当存在一条从房子 A 到房子 B 的路径时，称 B 从 A 可达。 Dixit 想在城市里买两套房子，一套用来居住，一套用来学习。当然，他希望能够在两套房子之间自由往返。因此，他想找到一对互达的房子 A 和 B。在所有这样的房子对中，他希望选择 $|k_A - k_B|$ 最大的一对，其中 $k_i$ 表示第 $i$ 个房子的入度。如果存在多个最优解，任选其一即可。 由于 Dixit 正在忙于准备 CodeCraft，你能帮他找到满足条件的房子对，或者告诉他不存在这样的房子对吗？ 在本题输入中，你不会被告知每条道路的方向。你只知道每个房子的入度 $k_i$。 你只允许向评测机询问一种类型的问题：给定两个房子 A 和 B，评测机会回答 B 是否可以从 A 到达。你可以询问的次数没有上限。但一旦评测机对你的某个询问回答了“Yes”，你就不能再继续提问。你也不能对同一个询问重复提问。 一旦你用完所有的询问（或者评测机对你的某个询问回答“Yes”），你的程序必须输出你猜测的两套房子的编号，然后立即退出。 详细交互说明见下文。

第一行包含一个整数 $n$（$3 \le n \le 500$），表示城市中的房子数量。 第二行包含 $n$ 个用空格分隔的整数 $k_1, k_2, \dots, k_n$（$0 \le k_i \le n-1$），其中第 $i$ 个数表示第 $i$ 个房子的入度。

要进行一次询问，请输出 "? A B"（$1 \leq A,B \leq N, A\neq B$）。如果房子 B 可以从房子 A 到达，评测机会回复“Yes”，否则回复“No”。 要输出最终答案，请输出 "! A B"，其中 A 和 B 是互达且 $|k_A - k_B|$ 最大的房子编号。如果不存在这样的房子对，输出 "! 0 0"。 在输出最终答案后，你的程序必须立即终止，否则会收到 Wrong Answer 判定。 你不能对同一个询问重复提问。你可以询问的次数没有上限，但一旦评测机对你的某个询问回答“Yes”，你就不能再继续提问。此时你的程序必须输出最终答案（"! A B" 或 "! 0 0"）并终止。 如果你的询问格式不正确或重复了之前的询问，你会收到 Wrong Answer 判定。 每次输出询问后不要忘记输出换行并刷新输出。否则你会收到 Idleness limit exceeded 错误。具体做法如下： - 在 C++ 中使用 fflush(stdout) 或 cout.flush()； - 在 Java 中使用 System.out.flush()； - 在 Pascal 中使用 flush(output)； - 在 Python 中使用 stdout.flush()； - 其他语言请查阅相关文档。

在第一个样例输入中，给出了一个有三个房子的城市，每个房子的入度都是 1。用户程序询问了一次 "? 1 2"，即询问能否从房子 1 到达房子 2。评测机回复“Yes”。用户程序认为这已经足够确定答案，于是输出 "! 1 2" 并退出。 在第二个样例输入中，用户程序对六对不同的房子进行了询问，最终输出 "! 0 0"，因为它确信在这个城市中不存在满足条件的房子对。 由 ChatGPT 4.1 翻译