【NOI2024】百万富翁 - 题目 - Universal Online Judge

这是一道交互题。

小 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$ 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$ ，下面是一个正确的交互过程：

选手程序	交互库	说明
调用 `richest(4,100,100)`	开始测试
调用 `ask([0,2],[1,3])`	返回 $[1, 2]$	$W_{0} < W_{1}, W_{2} > W_{3}$
调用 `ask([0,2,3],[1,1,1])`	返回 $[1, 1, 1]$	$W_{0} < W_{1}, W_{2} < W_{1}, W_{3} < W_{1}$
运行结束并返回 $1$	向屏幕打印交互结果	交互结束，结果正确

在这个例子中， $r = 1, t = 2, s = 5$ 满足请求与查询次数的限制。

下发文件说明

在本试题目录下：

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

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

数据范围

对于所有测试数据保证：所有 $W_{i}$ 两两不同。

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

测试点编号	分值	$N =$	$T =$	$S =$
$1$	$15$	$1000$	$1$	$499500$
$2$	$85$	$1000000$	$20$	$2000000$

评分方式

注意：

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

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

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

在上述条件基础上：

在测试点 $1$ 中，程序得到满分当且仅当 ask 函数调用合法且 richest 函数返回的答案正确；
在测试点 $2$ 中，程序得到的分数将按照以下方式计算：
- 若 ask 函数调用不合法，则获得 $0$ 分；
- 若 ask 函数调用均合法，设 $max t$ 表示多次调用 richest 函数所得的 $t$ 的最大值， $max s$ 表示 $s$ 的最大值，则程序将获得 $⌊ 85 \cdot f (max t) \cdot g (max s) ⌋$ 分，其中 $f$ 与 $g$ 的计算方式如下表所示：

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

$max s$	$g (max s)$
$max s \leq 1099944$	$1$
$1099945 \leq max s \leq 1100043$	$1 - \frac{1}{6} \log_{10} (max s - 1099943)$
$1100044 \leq max s \leq 2000000$	$\frac{2}{3} - \frac{1}{1500} \sqrt{max s - 1100043}$

以下是测试点 $2$ 中，不同的 $t$ 和 $s$ 对得分影响的示例。

$max t$	$max s$	测试点 $2$ 的得分
$= 20$	$\leq 1099944$	$11$
$= 19$		$14$
$= 18$		$17$
$= 17$		$21$
$= 16$		$24$
$= 15$		$28$
$= 14$		$32$
$= 13$		$37$
$= 12$		$42$
$= 11$		$48$
$= 10$		$54$
$= 9$		$63$
$\leq 8$	$\in [1099974, 1099978]$	$63$
	$\in [1099969, 1099973]$	$64$
	$\in [1099965, 1099968]$	$65$
	$\in [1099962, 1099964]$	$66$
	$\in [1099959, 1099961]$	$67$
	$\in [1099957, 1099958]$	$68$
	$\in [1099955, 1099956]$	$69$
	$\in [1099953, 1099954]$	$70$
	$= 1099952$	$71$
	$= 1099951$	$72$
	$\in [1099949, 1099950]$	$73$
	$= 1099948$	$75$
	$= 1099947$	$76$
	$= 1099946$	$78$
	$= 1099945$	$80$
	$\leq 1099944$	$85$

时间限制： $6 s 12 s$

空间限制： $512 MB$

Universal Online Judge

UOJ