P11423 [清华集训 2024] 阿尔塔尔 2

**这是一道交互题。** 请在提交时不要引用 `altar.h`。 --- 一年过去了，阿尔塔尔站在曾被他摧毁的祭坛面前。祭坛上的宝石早已失去了原有的光泽。 “解铃还须系铃人，是这样吗？”他喃喃自语。

祭坛呈正 $n$ 边形，每个顶点上有一个未激活的宝石。我们用 $1$ 至 $n$ 的整数给每种宝石编号。 宝石之间存在着能量流动关系，这使得激活一些宝石之后可以更容易地激活其他宝石。对于每一对宝石 $(i, j)$（$i\neq j$），要么从 $i$ 到 $j$ 存在流动，要么从 $j$ 到 $i$ 存在流动，即当我们把宝石看作点、从 $p$ 到 $q$ 的流动看作一条从 $p$ 到 $q$ 的有向边，得到的图是一个 $n$ 个点的**竞赛图**。阿尔塔尔并不知道宝石之间的能量流动关系如何。 为了激活祭坛，阿尔塔尔需要激活所有的宝石。为此，阿尔塔尔需要首先选择 $n$ 个宝石中的一个将其初始激活，然后进行若干次**能量传递**。每一次**能量传递**的效果为：若这次**能量传递**前宝石 $y$ 未被激活，且存在一个激活的宝石 $x$ 到 $y$ 有流动，那么**能量传递**后 $y$ 就会被激活。在**能量传递**前就被激活的宝石在**能量传递**之后依然是被激活的。 由于**能量传递**需要耗费大量体力，阿尔塔尔希望找到一个宝石，将其初始激活之后可以使用**最少次数的能量传递**激活所有宝石。为此，阿尔塔尔可以进行若干次**能量感知**：给出 $1 ≤ i, j ≤ n$ 且 $i\neq j$，一次**能量感知**可以确定宝石 $i$ 和 $j$ 之间的能量流动关系。 你需要帮助阿尔塔尔使用尽可能少的**能量感知**操作，确定初始激活的宝石编号。可以证明总是存在一个宝石，将其初始激活后使用有限次能量传递即可激活所有宝石。 ### 【实现细节】 你不需要也不应该实现主函数。你需要实现以下函数： ```cpp int altar(int n); ``` + 其中 $n$ 表示祭坛上的宝石数量。 + 你需要返回一个整数 $x$，表示阿尔塔尔需要初始激活宝石 $x$。你需要保证 $1 ≤ x ≤n$，且在所有宝石中初始激活 $x$ 可以让阿尔塔尔使用最少次数的**能量传递**激活所有宝石。 + **在最终测试时，交互库会在一次运行中调用 $T = 300$ 次 `altar` 函数。** 你可以调用以下函数进行**能量感知**： ```cpp bool sense(int i, int j); ``` + 你需要保证 $1 ≤ i, j ≤ n$ 且 $i\neq j$。 + 若 $i$ 与 $j$ 的能量流动为 $i$ 向 $j$，其返回 `true`，否则返回 `false`。 + 你需要保证在一次 `altar` 的调用中 `sense` 的调用次数不超过 $4.5 × 10^4$。 在满足题目条件和数据范围的情况下，最终测试时交互库的运行时间不会超过 $150\text{ ms}$，运行空间不会超过 $256\text{ MiB}$。 **交互库不是自适应的，即能量流动关系是固定的，不会随着交互过程改变。** ### 【测试程序方式】 **试题目录下的 `grader.cpp` 是我们提供的交互库参考实现。最终测试的交互库与样例交互库有一定不同，故你的实现不应该依赖样例交互库实现。** 你需要在本题目录下使用如下命令编译得到可执行程序： ``` g++ grader.cpp sample.cpp -o sample -O2 --std=c++14 -lm ``` 对于编译得到的可执行程序：

可执行文件将从标准输入读入以下格式的数据： – 第一行一个整数 $n$ 表示祭坛上的宝石数，你需要保证 $3 ≤ n ≤ 300$。 – 接下来 $n$ 行，第 $i$ 行一个长度为 $n$ 的 `01` 字符串，其中第 $j(j\neq i)$ 个字符为 `1` 表示能量流动从 $i$ 到 $j$，否则表示能量流动从 $j$ 到 $i$。你需要保证第 $i$ 行第 $j$ 个字符和第 $j$ 行第 $i$ 个字符间恰好有一个为 `1` 另一个为 `0`，**样例交互库并不会判断输入是否满足条件。** 读入完成之后，交互库将调用恰好一次函数 `altar`。

在 `altar` 函数退出后，如果你给出了正确的宝石编号，交互库将在标准输出流输出 `Correct. X`，其中 $X$ 表示 `sense` 的调用次数，并在标准错误流输出你返回的宝石编号以及对应的**能量传递**次数；否则交互库将在标准输出流输出 `Wrong Answer` 并在标准错误流输出对应错误信息。

### 【样例 1 解释】 该样例输出为下发的样例程序在该组样例下的输出。该样例中，`altar` 返回 $1$、$2$、$4$ 均满足条件。 ### 【子任务】 对于所有测试数据，单个测试点中 `altar` 函数的调用次数 $T = 300$，每一次调用都有 $3 ≤ n ≤ 300$。 子任务 $1$（$10$ 分，共 $1$ 个测试点）：$n = 300$，两个宝石之间的能量流动方向在两种可能间独立均匀随机。\ 子任务 $2$（$10$ 分，共 $2$ 个测试点）：存在一个宝石流向所有其他宝石。\ 子任务 $3$（$80$ 分，共 $7$ 个测试点）：没有特殊限制，依赖子任务 $1$、$2$。 ### 【评分方式】 **本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。 对于每个测试点，如果你的程序出现了非法的函数调用，或没有在所有测试数据中都返回正确的宝石，你将获得该测试点 $0\%$ 的分数。否则你会按照在 $T$ 组 `altar` 调用中的 `sense` 调用次数的**平均值** $X$，依据如下公式计算该测试点的得分占比： + 若 $45000 ≥ X ≥ 10^4$，你可以获得 $\left(1 + 29 × \frac{45000-X}{35000}\right)\%$ 的分数； + 若 $10^4 > X ≥ 2100$，你可以获得 $\left(30 + 30 ×\frac{10^4-X}{7900}\right)\%$ 的分数； + 若 $2100 > X ≥ 700$，你可以获得 $\left(60 + 20 ×\left(\frac{2100}X - 1\right)\right)\%$ 的分数； + 若 $X ≤ 700$，你可以获得该测试点 $100\%$ 的分数； 每个子任务的分数为该子任务中所有测试点的得分占比的最小值与该子任务满分的乘积。 **选手不应通过非法方式获取交互库的内部信息，如试图与标准输入、输出流进行交互。此类行为将被视为作弊。**