题目描述

小 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，可在程序开头加入以下代码实现：

#include "richest.h"

选手需要实现以下函数：

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

• $N$ 表示客户的数量；
• $T$ 表示对于当前函数调用，请求数 $t$ 不应超过此值；
• $S$ 表示对于当前函数调用，所有请求的查询次数总和 $s$ 不应超过此值；
• 该函数需要返回存款最多的客户的编号；
• 对于每个测试点，该函数会被交互库调用恰好 $10$ 次。

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

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

• 在调用 ask 函数时需要保证传入参数 $a$ 和 $b$ 的长度相同，且其中的每个元素都必须是小于 $N$ 的非负整数，表示该请求中的所有查询。
• 该函数会返回一个类型为 std::vector<int> 且长度与 $a$ 和 $b$ 相同的变量，设为 $c$，其中 $c[i]$ 表示在客户 $a[i]$ 和 $b[i]$ 中存款较多的客户的编号。

题目保证在规定的请求和查询次数限制下，交互库运行的时间不超过 $3$ 秒，交互库使用的内存大小固定，且不超过 $256\text{ MiB}$。

---

数据范围

对于所有测试数据保证：所有 $W_i$ 两两不同。

本题共 $2$ 个测试点，每个测试点的分值和数据范围见下表。

测试点编号	分值	$N=$	$T=$	$S=$
$1$	$15$	$1\,000$	$1$	$499\,500$
$2$	$85$	$1\,000\,000$	$20$	$2\,000\,000$

---

评分方式

注意：

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

在每次 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$ 的计算方式如下表所示：

$\max t$	$f(\max t)$
$\max t \leq 8$	$1$
$9 \leq \max t \leq 20$	$1-\dfrac{1}{4}\sqrt{\max t-8}$

$\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$ 对得分影响的示例。

$\max t$	$\max s$	测试点 2 的得分
$=20$	$\le 1\,099\,944$	$11$
$=19$		$14$
$=18$		$17$
$=17$		$21$
$=16$		$24$
$=15$		$28$
$=14$		$32$
$=13$		$37$
$=12$		$42$
$=11$		$48$
$=10$		$54$
$=9$		$63$
$\le 8$	$\in [1\,099\,974,1\,099\,978]$	$64$
	$\in [1\,099\,969,1\,099\,973]$
	$\in [1\,099\,965,1\,099\,968]$	$65$
	$\in [1\,099\,962,1\,099\,964]$	$66$
	$\in [1\,099\,959,1\,099\,961]$	$67$
	$\in [1\,099\,957,1\,099\,958]$	$68$
	$\in [1\,099\,955,1\,099\,956]$	$69$
	$\in [1\,099\,953,1\,099\,954]$	$70$
	$=1\,099\,952$	$71$
	$=1\,099\,951$	$72$
	$\in [1\,099\,949,1\,099\,950]$	$73$
	$=1\,099\,948$	$75$
	$=1\,099\,947$	$76$
	$=1\,099\,946$	$78$
	$=1\,099\,945$	$80$
	$\le 1\,099\,944$	$85$

---