P10786 [NOI2024] 百万富翁

**本题仅支持 C++ 语言评测。由于平台限制，使用 C++14 (GCC 9) 提交代码会导致 CE。请使用其他版本的 C++ 提交（推荐 C++14 及以上）。** 与 NOI 要求的提交格式不同，你的程序中**不应该**包含头文件 `richest.h`。同时，你的程序中应当在包含 `vector` 头文件的前提下，包含对以下函数的声明： ```cpp std::vector ask(std::vector a, std::vector b); ``` 除此之外，其余要求与 NOI 要求一致。

小 Y 的银行有 $N$ 个客户，编号为 $0$ 到 $N-1$。客户 $i$ 有 $W_i$ 元存款，且**客户之间的存款金额互不相同**。 小 P 是小 Y 的深度合作伙伴，他希望知道哪个客户的存款最多。小 P 无法直接获取客户的存款金额，但他可以依次发送若干次**请求**，每次请求包含若干个**查询**，每个查询是一个二元组 $(i,j)$，表示小 P 想知道客户 $i$ 和客户 $j$ 的存款金额哪个更多。如果 $W_i>W_j$，小 Y 会回答 $i$，否则回答 $j$。 小 P 的**请求数** $t$ 和所有请求的**查询**次数总和 $s$ 有上限，他希望你帮他写一个程序，来找到存款最多的客户。

选手不需要，也不应该实现 main 函数。 选手应确保提交的程序包含头文件 `richest.h`，可在程序开头加入以下代码实现： ```cpp #include "richest.h" ``` 选手需要实现以下函数： ```cpp int richest(int N,int T,int S); ``` - $N$ 表示客户的数量； - $T$ 表示对于当前函数调用，**请求**数 $t$ 不应超过此值； - $S$ 表示对于当前函数调用，所有请求的**查询**次数总和 $s$ 不应超过此值； - 该函数需要返回存款最多的客户的编号； - 对于每个测试点，该函数**会被交互库调用恰好 $10$ 次**； 选手可以通过调用以下函数向交互库发送一次**请求**： ```cpp std::vector ask(std::vector a, std::vector b); ``` - 在调用 `ask` 函数时需要保证传入参数 $a$ 和 $b$ 的长度相同，且其中的每个元素都必须是小于 $N$ 的非负整数，表示该**请求**中的所有**查询**。 - 该函数会返回一个类型为 `std::vector ` 且长度与 $a$ 和 $b$ 相同的变量，设为 $c$，其中 $c[i]$ 表示在客户 $a[i]$ 和 $b[i]$ 中存款较多的客户的编号。 题目保证在规定的**请求**和**查询**次数限制下，交互库运行的时间不超过 $3$ 秒，交互库使用的内存大小固定，且不超过 $256$ MiB。 **试题目录下的 `grader.cpp` 是提供的交互库参考实现，最终测试所用的交互库与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。** 选手可以在本题目录下使用如下命令编译得到可执行程序： ``` g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static ``` 对于编译得到的可执行程序： - 可执行文件将从**标准输入**读入以下格式的数据： - 输入的第一行包含四个非负整数 $N,T,S,R$，其中 $R$ 是交互库生成测试数据的随机种子。 - 输入完成后，交互库将调用 $10$ 次函数 `richest`，用输入的参数生成的测试数据进行测试。`richest` 函数返回后，交互库会输出以下信息： - 输出的前 $10$ 行中，每行首先包含三个整数 $r,t,s$，表示该次执行的结果。其中 $r$ 是 `richest` 函数的返回值，$t$ 和 $s$ 的含义如题目描述中所示，然后包含该次运行的正确性等消息。 - 输出的第 $11$ 行包含 $10$ 次运行的总信息。

假设可执行文件生成的测试数据为 $N=4$，$W=[101,103,102,100]$，$T=100$，$S=100$，下面是一个正确的交互过程： ::cute-table{tuack} | 选手程序 | 交互库 | 说明 | | :----------: | :----------: | :----------: | | | 调用 `richest(4,100,100)` | 开始测试 | | 调用 `ask([0,2],[1,3])` | 返回 $[1,2]$ | $W_0W_3$ | | 调用 `ask([0,2,3],[1,1,1])` | 返回 $[1,1,1]$ | $W_0

**【下发文件说明】** 在本试题目录下： - `grader.cpp` 是提供的交互库参考实现。 - `richest.h` 是头文件，选手不用关心具体内容。 - `template_richest.cpp` 是提供的示例代码，选手可在此代码的基础上实现。 选手注意对所有下发文件做好备份，最终评测时只测试本试题目录下的 `richest.cpp`，对该程序以外文件的修改不会影响评测结果。 **【数据范围】** 对于所有测试数据保证：所有 $W_i$ 两两不同。 本题共 $2$ 个测试点，每个测试点的分值和数据范围见下表。 ::cute-table{tuack} | 测试点编号 | 分值 | $N=$ | $T=$ | $S=$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $15$ | $1\,000$ | $1$ | $499\,500$ | | $2$ | $85$ | $1\,000\,000$ | $20$ | $2\,000\,000$ | **【评分方式】** 注意： - 选手不应通过非法方式获取交互库的内部信息，如试图直接读取数组 $W$ 的值，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。 - **最终的评测交互库与样例交互库的实现不同，且可能是适应性的：在不与 `ask` 此前返回的结果相矛盾的前提下，最终的评测交互库可能会动态调整 $W$ 的值。** **本题首先会受到和传统相同的限制**。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 0 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。 在每次 `richest` 函数调用中，程序使用的请求次数 $t$ 和所有请求的查询次数总和 $s$ 需在对应限制下，否则将会获得 $0$ 分。 在上述条件基础上： - 在测试点 $1$ 中，程序得到满分当且仅当 `ask` 函数调用合法且 `richest` 函数返回的答案正确； - 在测试点 $2$ 中，程序得到的分数将按照以下方式计算： - 若 `ask` 函数调用不合法，则获得 $0$ 分； - 若 `ask` 函数调用均合法，设 $\max t$ 表示多次调用 `richest` 函数所得的 $t$ 的最大值，$\max s$ 表示 $s$ 的最大值，则程序将获得 $\lfloor 85 \cdot f(\max t) \cdot g(\max s)\rfloor$ 分，其中 $f$ 与 $g$ 的计算方式如下表所示： ::cute-table{tuack} | $\max t$ | $f(\max t)$ | | :----------: | :----------: | | $\max t\leq 8$ | $1$ | | $9\leq \max t\leq 20$ | $1-\dfrac{1}{4}\sqrt{\max t-8}$ | ::cute-table{tuack} | $\max s$ | $g(\max s)$ | | :----------: | :----------: | | $\max s\leq 1\,099\,944$ | $1$ | | $1\,099\,945\leq \max s\leq 1\,100\,043$ | $1-\dfrac{1}{6} \log_{10} (\max s-1\,099\,943)$ | | $1\,100\,044\leq \max s\leq 2\,000\,000$ | $\dfrac{2}{3}-\dfrac{1}{1\,500}\sqrt{\max s-1\,100\,043}$| 以下是测试点 $2$ 中，不同的 $t$ 和 $s$ 对得分影响的示例。 ::cute-table{tuack} | $\max t$ | $\max s$ | 测试点 $2$ 的得分 | | :------: | :----------------------------: | :---------------: | | $=20$ | $\le 1\,099\,944$ | $11$ | | $=19$ | $\le 1\,099\,944$ | $14$ | | $=18$ | $\le 1\,099\,944$ | $17$ | | $=17$ | $\le 1\,099\,944$ | $21$ | | $=16$ | $\le 1\,099\,944$ | $24$ | | $=15$ | $\le 1\,099\,944$ | $28$ | | $=14$ | $\le 1\,099\,944$ | $32$ | | $=13$ | $\le 1\,099\,944$ | $37$ | | $=12$ | $\le 1\,099\,944$ | $42$ | | $=11$ | $\le 1\,099\,944$ | $48$ | | $=10$ | $\le 1\,099\,944$ | $54$ | | $=9$ | $\le 1\,099\,944$ | $63$ | | $\le 8$ | $\in [1\,099\,974,1\,099\,978]$ | $63$ | | $\le 8$ | $\in [1\,099\,969,1\,099\,973]$ | $64$ | | $\le 8$ | $\in [1\,099\,965,1\,099\,968]$ | $65$ | | $\le 8$ | $\in [1\,099\,962,1\,099\,964]$ | $66$ | | $\le 8$ | $\in [1\,099\,959,1\,099\,961]$ | $67$ | | $\le 8$ | $\in [1\,099\,957,1\,099\,958]$ | $68$ | | $\le 8$ | $\in [1\,099\,955,1\,099\,956]$ | $69$ | | $\le 8$ | $\in [1\,099\,953,1\,099\,954]$ | $70$ | | $\le 8$ | $=1\,099\,952$ | $71$ | | $\le 8$ | $=1\,099\,951$ | $72$ | | $\le 8$ | $\in [1\,099\,949,1\,099\,950]$ | $73$ | | $\le 8$ | $=1\,099\,948$ | $75$ | | $\le 8$ | $=1\,099\,947$ | $76$ | | $\le 8$ | $=1\,099\,946$ | $78$ | | $\le 8$ | $=1\,099\,945$ | $80$ | | $\le 8$ | $\le 1\,099\,944$ | $85$ |