P10786 [NOI2024] Millionaire

**This problem only supports judging in C++. Due to platform limits, submitting with C++14 (GCC 9) will cause CE. Please submit using other C++ versions (C++14 or later is recommended).** Different from NOI’s required submission format, your program **should not** include the header file `richest.h`. Also, on the premise that your program includes the `vector` header, it should declare the following function: ```cpp std::vector ask(std::vector a, std::vector b); ``` Other requirements are the same as NOI’s requirements.

Xiao Y’s bank has $N$ clients, numbered from $0$ to $N-1$. Client $i$ has a deposit of $W_i$ yuan, and **all clients’ deposit amounts are pairwise distinct**. Xiao P is Xiao Y’s close partner, and he wants to know which client has the most deposit. Xiao P cannot directly obtain the deposit amounts, but he can send several **requests** one by one. Each request contains several **queries**. Each query is an ordered pair $(i,j)$, meaning that Xiao P wants to know which of client $i$ and client $j$ has more deposit. If $W_i>W_j$, Xiao Y answers $i$, otherwise he answers $j$. Xiao P has upper limits on the number of **requests** $t$ and the total number of **queries** across all requests $s$. He wants you to write a program to find the client with the largest deposit.

You do not need to, and should not, implement the `main` function. You should ensure that the submitted program includes the header file `richest.h`. You may add the following code at the beginning of your program: ```cpp #include "richest.h" ``` You need to implement the following function: ```cpp int richest(int N,int T,int S); ``` - $N$ is the number of clients. - $T$ means that, for the current call, the number of **requests** $t$ must not exceed this value. - $S$ means that, for the current call, the total number of **queries** across all requests $s$ must not exceed this value. - The function should return the index of the client with the largest deposit. - For each test point, this function **will be called by the interactive library exactly $10$ times**. You can send one **request** to the interactive library by calling the following function: ```cpp std::vector ask(std::vector a, std::vector b); ``` - When calling `ask`, you must ensure that the lengths of parameters $a$ and $b$ are the same, and every element in them must be a non-negative integer less than $N$, representing all **queries** in this **request**. - The function returns a `std::vector ` with the same length as $a$ and $b$. Denote it by $c$, where $c[i]$ is the index of the client with the larger deposit between clients $a[i]$ and $b[i]$. The problem guarantees that under the given limits on **requests** and **queries**, the interactive library runs in at most $3$ seconds. The interactive library’s memory usage is fixed and does not exceed $256$ MiB. **`grader.cpp` in the problem directory is a reference implementation of the interactive library. The interactive library used in the final tests is different from the reference implementation, so your solution should not rely on how the interactive library is implemented.** You can compile an executable in this problem directory using the following command: ``` g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static ``` For the compiled executable: - The executable will read input from **standard input** in the following format: - The first line contains four non-negative integers $N,T,S,R$, where $R$ is the random seed used by the interactive library to generate testdata. - After reading the input, the interactive library will call the function `richest` $10$ times, and test it on testdata generated from the input parameters. After `richest` returns, the interactive library will output the following information: - In the first $10$ output lines, each line first contains three integers $r,t,s$, indicating the result of that run. Here $r$ is the return value of `richest`, and the meanings of $t$ and $s$ are as described above, followed by messages about correctness, etc. - The $11$-th line contains the overall information of the $10$ runs.

Suppose the testdata generated by the executable is $N=4$, $W=[101,103,102,100]$, $T=100$, $S=100$. Below is a correct interactive process: ::cute-table{tuack} | Contestant Program | Interactive Library | Explanation | | :----------: | :----------: | :----------: | | | Call `richest(4,100,100)` | Start testing. | | Call `ask([0,2],[1,3])` | Return $[1,2]$ | $W_0W_3$. | | Call `ask([0,2,3],[1,1,1])` | Return $[1,1,1]$ | $W_0

**[Files Provided]** In this problem directory: - `grader.cpp` is a reference implementation of the interactive library. - `richest.h` is a header file; contestants do not need to care about its contents. - `template_richest.cpp` is sample code; contestants may implement their solution based on it. Please back up all provided files. In the final judging, only `richest.cpp` in this problem directory will be tested. Modifying files other than this program will not affect the judging result. **[Constraints]** For all testdata, it is guaranteed that all $W_i$ are pairwise distinct. This problem has $2$ test points. The score and constraints for each test point are shown in the table below. ::cute-table{tuack} | Test Point ID | Score | $N=$ | $T=$ | $S=$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $15$ | $1\,000$ | $1$ | $499\,500$ | | $2$ | $85$ | $1\,000\,000$ | $20$ | $2\,000\,000$ | **[Scoring]** Notes: - Contestants must not obtain internal information from the interactive library by illegal means, such as trying to directly read the values of array $W$, or interacting directly with standard input/output streams. Such behavior will be considered cheating. - **The interactive library used in the final judging is different from the sample interactive library, and may be adaptive: as long as it does not contradict results previously returned by `ask`, the final interactive library may dynamically adjust the values of $W$.** **This problem is first subject to the same limits as traditional problems**. For example, a compile error results in $0$ points for the whole problem; runtime errors, exceeding the time limit, or exceeding the memory limit will all result in $0$ points for the corresponding test point. Contestants may only access variables or data defined by themselves and provided by the interactive library, as well as their corresponding memory. Attempting to access other memory locations may lead to compile errors or runtime errors. In each call to `richest`, the number of requests used $t$ and the total number of queries across all requests $s$ must be within the corresponding limits; otherwise, you will get $0$ points. Based on the above conditions: - In test point $1$, you get full score if and only if calls to `ask` are legal and `richest` returns the correct answer. - In test point $2$, your score will be calculated as follows: - If any call to `ask` is illegal, you get $0$ points. - If all calls to `ask` are legal, let $\max t$ be the maximum $t$ among the multiple calls to `richest`, and let $\max s$ be the maximum $s$. Then the program gets $\lfloor 85 \cdot f(\max t) \cdot g(\max s)\rfloor$ points, where $f$ and $g$ are computed as in the tables below: ::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}$| Below are examples in test point $2$ showing how different $t$ and $s$ affect the score. ::cute-table{tuack} | $\max t$ | $\max s$ | Score for Test Point $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$ | Translated by ChatGPT 5