[湖北省选模拟 2024] 白草净华 / buer

**由于洛谷评测环境限制，请勿使用 C++ 14 (GCC 9) 语言提交本题，否则可能会导致编译错误。** **这是一道交互题。** 神明只送给人类填饱肚子的知识，人类却借此制作了工具，书写了文字，壮大了城邦，现在又放眼星辰与深渊…… 他们每时每刻都在创造全新的「知识」，也令我再也无法移开双眼。 我自认为我擅长提问和回答问题，但我渐渐明白，有很多人是揣着明白装糊涂，问题的答案并不能帮上他们的忙。是不是随着年龄增长，大家都会失去面对质问和答案的勇气呢……

智慧之神布耶尔的知识可以用长度为 $N$ 的数列 $a_0,a_1,\cdots,a_{N-1}$ 表示（请注意，下标从 $0$ 开始）。很遗憾，凡人难以窥探智慧之神的知识，你既不知道 $N$ 的大小，又不知道任何 $a_i$ 的值。 智慧之神是善良的，纳西妲愿意告诉你关于知识的一切： - 对于任意的 $0 \le i < N$，$a_i \neq a_{(i+1)\bmod N}$。 - **有且仅有一个** $i(0 \le i < N)$，使 $a_i>a_{(i+1)\bmod N}$ 与 $a_i > a_{(i+N-1)\bmod N}$ 同时成立。 你可以向智慧之神提问，每次提问，你可以向纳西妲提供一个 $0\sim10^9$ 范围内的整数 $k$，纳西妲将回答你 $a_{(d+k)\bmod N}$ 的值。其中，$d$ 是上一次纳西妲回答的元素的下标。$d$ 的初始值设定为 $0$。例如，$N=5$，你依次向纳西妲提供了 $1,2,3$，纳西妲回答的数字依次为 $a_1,a_3,a_1$。 你有 $333$ 次提问的机会，你需要求出数列 $a$ 中的最大值。 你，还有质问与提问的勇气吗？ ### 实现细节 交互库实现了如下函数，**选手需要在程序中声明这些函数，但不应该实现其函数体**： ```cpp int ask(int k); ``` - 这个函数返回 $a_{(d+k)\bmod N}$ 的值，并将 $d$ 的值修改为 $d+k$。 ```cpp int cheat(); ``` - 这个函数返回 $N$ 的值。 - **调用该函数，将不能得到测试点全部的分数，详见评分方式部分。** **你不需要，也不应该实现主函数。** 你需要实现函数 `buer`： ```cpp int buer(int T); ``` - `T` 表示测试点编号。 - 你需要在函数结束时，返回数列 $a$ 的最大值。 **此外，你提交的程序不应试图从或向任何文件或标准控制流读取或写入信息，否则本题以零分计。** 你的程序需要引用全部你所需要的头文件与命名空间。 最终测试时，在每个测试点，交互库会恰好调用一次 `buer` 函数，并将其返回值作为你程序的结果。 下面是一个示例程序，其功能是获取 $a_1 \sim a_9$ 并返回 $\max(a_1,a_2)$。选手可以在此基础上继续实现本题。 ```cpp #include <vector> using std::max; using std::vector; // 引用所需头文件与命名空间中的函数 int ask(int k); int cheat(); // 声明 ask 与 cheat 函数 int buer(int T) { vector <int> vec; for(int i = 1; i <= 9; i++) { int p = ask(1); vec.push_back(p); } return max(vec[0], vec[1]); } ``` **保证在 `ask` 函数调用不超过 $3333$ 次的情况下，最终测试的交互库运行所需时间不超过 $0.2$ 秒，交互库本身所消耗的内存不超过 $10$ MiB。** ### 测试程序方式 本题目录下提供了交互库的参考实现 `grader.cpp`。最终测试时所使用的交互库实现与该实现有所不同，因此选手的解法**不应依赖交互库的具体实现**。 选手实现程序 `buer.cpp` 后，将 `grader.cpp` 与 `buer.cpp` 放置在同一目录下，使用如下命令编译得到可执行程序： ```plain g++ -c grader.cpp -O2 -std=c++14 g++ -c buer.cpp -O2 -std=c++14 g++ grader.o buer.o -o buer -O2 -std=c++14 ``` 其中第一行命令会编译 `grader.cpp` 得到目标文件 `grader.o`，第二行命令会编译 `buer.cpp` 得到目标文件 `buer.o`，第三行命令会将 `grader.o` 与 `buer.o` 链接起来，生成可执行文件 `buer`。 按上述方法编译得到的可执行文件 `buer`，其运行方式如下： - 可执行文件将从 `buer.in` 读入以下格式的数据： - - 第一行为两个正整数 $N,T$，分别表示 $a$ 的长度与测试点编号。 - - 第二行为 $N$ 个正整数 $a_0,a_1,\ldots,a_{N-1}$，表示数列 $a$。 - 若你的程序正常运行完毕，可执行文件将向 `buer.out` 写入以下内容： - - 输出一行两个整数，分别表示你的询问次数与 `buer` 函数的返回值。 选手在调试时需要保证输入可执行文件 `buer` 的数据满足上述格式，否则不保证交互库正确运行。

你提交的程序不应试图从或向任何文件或标准控制流读取或写入信息。

你提交的程序不应试图从或向任何文件或标准控制流读取或写入信息。

4 0
1 2 3 2

3

### 样例解释 1 本题提供的样例输入中，第一行为两个整数 $N,T$，分别表示 $N$ 与测试点编号，样例测试点编号均为 $0$。第二行为 $N$ 个整数 $a_0,a_1,\cdots,a_{N-1}$，表示数列 $a$。样例输出为一行一个正整数，表示数列 $a$ 的最大值。 **请注意，你的程序不应试图从或向任何文件或标准控制流读取或写入信息。** ### 评分方式 最终评测**只**收取 `buer.cpp`，请不要提交选手目录下其他文件。 **本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 $0$ 分，运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。 在上述条件以外，在一个测试点中，若程序执行了非法的函数调用或 `buer` 函数返回了错误答案，该测试点将会获得 $0$ 分。否则，假设你的程序调用了 $Q$ 次 `ask` 函数： - 若 $0 \le Q \le 333$，且没有调用 `cheat` 函数，该测试点得 $5$ 分。 - 若 $333<Q\le 3333$，且没有调用 `cheat` 函数，该测试点得 $3$ 分。 - 若 $0\le Q \le 333$，但调用了 `cheat` 函数，该测试点得 $2$ 分。 - 若 $333<Q\le 3333$，但调用了 `cheat` 函数，该测试点得 $1$ 分。 - 若 $Q>3333$，该测试点得 $0$ 分。 ### 子任务 对于所有测试数据，保证 $2 \le N \le 10^6$，$1 \le a_i \le 10^9$。 | 测试点编号 | $N\le$ | | :--: | :--: | | $1$ | $333$ | | $2\sim 20$ | $10^6$ |