#10000217. 【NOI 2024 Day 1】百万富翁（richest）

提交源程序文件名

这是一道交互题。

【题目描述】

小 Y 的银行有 个客户，编号为 到 。客户 有 元存款，且客户之间的存款金额互不相同。

小 P 是小 Y 的深度合作伙伴，他希望知道哪个客户的存款最多。小 P 无法直接获取客户的存款金额，但他可以依次发送若干次请求，每次请求包含若干个查询，每个查询是一个二元组 ，表示小 P 想知道客户 和客户 的存款金额哪个更多。如果 ，小 Y 会回答 ，否则回答 。

小 P 的请求数 和所有请求的查询次数总和 有上限，他希望你帮他写一个程序来找到存款最多的客户。

【实现细节】

选手不需要，也不应该实现 main 函数。 选手应确保提交的程序包含头文件 richest.h，可在程序开头加入以下代码实现：

#include "richest.h"

选手需要实现以下函数：

int richest(int N, int T, int S);

• 表示客户的数量；

• 表示对于当前函数调用，请求数 不应超过此值；

• 表示对于当前函数调用，所有请求的查询次数总和 不应超过此值；

• 该函数需要返回存款最多的客户的编号；

• 对于每个测试点，该函数会被交互库调用恰好 次.

选手可以通过调用以下函数向交互库发送一次请求：

std::vector<int> ask(std::vector<int> a, std::vector<int> b);

• 在调用 ask 函数时需要保证传入参数 和 的长度相同，且其中的每个元素都必须是小于 的非负整数，表示该请求中的所有查询；

• 该函数会返回一个类型为 std::vector<int> 且长度与 和 相同的变量，设为 。其中 表示在客户 和 中存款金额较多的客户的编号。

题目保证在规定的请求与查询次数限制下，交互库运行所需的时间不超过 秒；交互库使用的内存大小固定，且不超过 。

【测试程序方式】

试题目录下的 grader.cpp 是提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

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

g++ grader.cpp richest.cpp ‐o richest ‐O2 ‐std=c++14 ‐static

对于编译得到的可执行程序：

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

  • 输入的第一行包含四个非负整数 ，其中 是交互库生成测试数据的随机种子。

• 输入完成后，交互库将调用 次函数 richest，用输入的参数生成的测试数据进行测试。richest 函数返回后，交互库会输出以下信息；

  • 输出的前 行中，每行首先包含三个整数 ，表示该次执行的结果，其中 是 richest 函数的返回值， 和 的含义如题目描述中所示，然后包含该次运行的正确性等信息。

  • 输出的第 行包含 次运行的总信息。

【交互示例】

假设可执行文件生成的测试数据为 ，，，。

下面是一个正确的交互过程：

在这个例子中，，，，满足请求与查询次数的限制。

【下发文件说明】

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. richest.h 是头文件，选手不用关心具体内容。
3. template_richest.cpp 是提供的示例代码，选手可在此代码的基础上实现。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的richest.cpp，对该程序以外文件的修改不会影响评测结果。

【数据范围】

对于所有测试数据保证：所有 两两不同。 本题共 个测试点，每个测试点的分值和数据范围见下表。

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如试图直接读取数组W 的值，或直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同，且可能是适应性的：在不与 ask 此前返回的结果相矛盾的前提下，最终的评测交互库可能会动态调整 的值。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 分等。选手只能在程序中访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在每次 richest 函数调用中，选手程序使用的请求次数 和所有请求的查询次数总和 需在对应限制下，否则将会获得 分。

在上述条件基础上：

• 在测试点 中，程序得到满分当且仅当 ask 函数调用合法且 richest 函数返回的答案正确；

• 在测试点 中，程序得到的分数将按照以下方式计算：

  • 若 ask 函数调用不合法，则获得 分；

  • 若 ask 函数调用均合法，设 表示多次调用 richest 函数时所得的 的最大值， 表示 的最大值，则程序将获得 分，其中 与 的计算方式如下表所示：

以下是测试点 中，不同的 和 对得分影响的示例：