P1001风眼定位（locate）

本题为交互题。

【题目背景】

沿岸设施恢复后，观测阵列重新接收到风暴内部的信号。tfbz 对照海图确认，最强信号所在的位置就是风眼，于是准备借助尚未完全修复的观测装置确定风眼的位置。

【题目描述】

观测阵列上共有 $n$ 个位置，依次编号为 $1\sim n$。第 $i$ 个位置有一个隐藏的信号强度，所有位置的信号强度两两不同，其中信号最强的位置就是 tfbz 要寻找的风眼。

受损的观测装置无法直接找出一段区域内最强的信号。每次观测时，tfbz 可以选定两个整数 $l,r$，其中 $1\leq l<r\leq n$。观测装置会比较位置 $l,l+1,\ldots,r$ 的信号，并告诉 tfbz 其中第二强的信号位于整个阵列中的哪个位置。

tfbz 可以进行若干次观测。每次观测结束后，tfbz 都可以根据已经得到的结果决定下一次观测的区域。最后，tfbz 需要指出整个阵列中信号最强的位置。

每次启动观测装置都需要消耗一枚 Gioush 大队珍藏的魔力晶石。为了给抵御风暴留下足够的材料，tfbz 希望尽可能减少观测次数。你需要帮助 tfbz 制定观测策略，确定风眼所在的位置。

【实现细节】

选手不需要，也不应实现 main 函数。

选手需要确保提交的程序包含头文件 locate.h，即在程序开头加入以下代码：

1#include "locate.h"

选手需要在提交的程序源文件 locate.cpp 中实现以下两个函数：

1void Init(int c, int T);

• $c,T$ 分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

1int Locate(int c, int n);

• $c,n$ 分别表示测试点编号与观测位置的数量。
• 该函数需要返回一个正整数，表示整个阵列中信号强度最大的位置。
• 对于每组测试数据，该函数会被交互库调用恰好一次。

选手可以通过调用以下函数进行一次询问：

1int Query(int l, int r);

• $l,r$ 表示 tfbz 本次观测区域的左右端点。选手需要确保 $1\leq l<r\leq n$。
• 该函数会返回位置 $l,l+1,\ldots,r$ 中信号强度第二大的位置编号，具体含义如【题目描述】中所示。
• 选手需要确保交互库每次调用 Locate 时，调用该函数的次数不超过 $200$。

交互库运行所需的时间与空间均计入本题的时间与空间限制。

本试题目录下的 template_locate.cpp 是提供的示例代码，选手可以参考并实现自己的程序。

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行文件：

1g++ grader.cpp locate.cpp -o locate -O2 -std=c++14 -static

对于编译得到的可执行文件 locate：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。
  • 接下来对于每组测试数据，第一行包含一个正整数 $n$。
  • 第二行包含一个 $1\sim n$ 的排列，排列中的第 $i$ 个数表示位置 $i$ 的信号强度。

• 可执行文件将输出以下格式的数据至标准输出：

  • 若 $T$ 次调用 Locate 的返回值均正确，则：
    • 输出的第一行为 Correct!。
    • 输出的第二行为 Max queries used: Q，其中 $Q$ 表示所有测试数据中调用 Query 的次数的最大值。
    • 输出的第三行为 Score ratio: P%，其中 $P$ 表示按照【评分方式】计算出的得分比例。
  • 若至少一次调用 Locate 的返回值不正确，则只会输出一行 Wrong answer。

• 若调用 Query 时传入的参数不符合要求，或调用次数超过上限，则可执行文件会向标准错误流输出错误信息并终止程序。

【样例 1 输入】

10 22535 1 4 2 34251 2

【样例 1 输出】

1Correct!2Max queries used: 33Score ratio: 100%

【说明/提示】

【样例 1 解释】

对于第一组测试数据，依次调用 Query(1,5)、Query(1,3) 与 Query(2,3)，返回值分别为 $3,3,2$，于是可以确定最强信号位于位置 $1$。对于第二组测试数据，调用 Query(1,2) 得到 $1$，于是可以确定最强信号位于位置 $2$。两组测试数据中调用 Query 次数的最大值为 $3$。

【样例 2】

见选手目录下的 $\textbf{\textit{locate/locate2.in}}$ 和 $\textbf{\textit{locate/locate2.ans}}$。

该组样例符合测试点 $1$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{locate/locate3.in}}$ 和 $\textbf{\textit{locate/locate3.ans}}$。

该组样例符合测试点 $2$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{locate/locate4.in}}$ 和 $\textbf{\textit{locate/locate4.ans}}$。

该组样例符合测试点 $3$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 100$，$2\leq n\leq 10^5$，所有信号强度两两不同。

特殊性质 A：保证信号最强的位置为 $1$ 或 $n$。

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如试图直接读取各位置的信号强度，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。
• 交互库不是适应性的，即每次调用 Locate 时所有位置的信号强度就已经确定，不会随交互过程变化。
• 最终的评测交互库与样例交互库的实现不同。

若 Locate 函数的返回值不正确，或调用 Query 时不符合以上要求，则相应测试点得 $0$ 分。

在上述条件基础上：

• 对于每个测试点，设 $Q$ 表示各组测试数据中调用 Query 次数的最大值，$\text{score}$ 表示该测试点的分值，则程序获得 $p(Q)\times\text{score}$ 分，其中 $p(Q)$ 按照下表计算。