Background

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:

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

Other requirements are the same as NOI’s requirements.

Problem Description

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.

Input Format

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:

#include "richest.h"

You need to implement the following function:

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:

std::vector <int> ask(std::vector <int> a, std::vector <int> 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 <int> 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.

Output Format

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}

In this example, $r=1,t=2,s=5$, which satisfies the limits on requests and queries.

Hint

[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}

[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}

::cute-table{tuack}

Below are examples in test point $2$ showing how different $t$ and $s$ affect the score.

::cute-table{tuack}

Translated by ChatGPT 5