题目描述

两个玩家 A 和 B 玩如下游戏。

A 想好了一个排列：

$$p[1],p[2],\ldots,p[N]$$

它是 $1,2,\ldots,N$ 的一个排列，但 B 不知道这个排列。

B 可以进行如下询问：

在 $p[x]$ 和 $p[y]$ 中，哪个更大？

其中 $1\le x,y\le N$。

B 的目标是找出排列中最大的 $K$ 个数的位置，也就是数值

$$N,N-1,\ldots,N-K+1$$

在排列中的下标，并且希望使用尽可能少的询问次数。注意：前 $N-1$ 次询问不计入总询问代价。

评测程序将扮演玩家 A，你的程序将扮演玩家 B。

任务

请实现函数 biggest()，它将与评测程序一起编译。你的函数需要通过比较询问找出最大的 $K$ 个数的位置。

函数格式如下：

std::vector<int> biggest(int N, int K);

评测程序会调用一次该函数，参数含义如下：

• $N$：排列长度；
• $K$：需要找出的最大值个数。

函数需要返回一个长度为 $K$ 的向量，依次包含数值

$$N,N-1,\ldots,N-K+1$$

在排列中的下标。也就是说，返回的第一个元素是最大值 $N$ 的下标，第二个元素是 $N-1$ 的下标，依此类推。

交互函数

你可以调用如下函数与评测程序通信：

int compare(int x, int y);

其中 $1\le x,y\le N$。

函数返回：

• 若 $p[x]>p[y]$，返回 x；
• 否则返回 y。

你可以调用该函数任意多次，但如果某个测试点中调用次数超过 $3\,000\,000$，该测试点得 $0$ 分。

提交要求

你需要提交文件 biggest.cpp，其中包含函数 biggest()。

该文件可以包含其他辅助函数和代码，但不能包含 main() 函数。

文件开头需要包含：

#include "biggest.h"

数据范围

所有测试中：

$$N=100000$$

并且：

$$1\le K\le 100000$$

排列 $p$ 会随机生成，每个排列出现的概率相同。

评分方式

每个测试点单独评分。

对于某个测试点，若你的函数满足以下条件，则可以获得非零分：

• 在不超过 $3\,000\,000$ 次 compare 调用内结束；
• 返回长度为 $K$ 的向量；
• 返回的下标完全正确，并且顺序为从最大值到第 $K$ 大值。

设：

• yourScore 为你的程序在前 $N-1$ 次询问之后额外使用的询问次数；
• authorScore 为作者程序在前 $N-1$ 次询问之后额外使用的询问次数。

那么该测试点得分比例为：

$$\min\left(1,\frac{\text{authorScore}+1}{\text{yourScore}+1}\right)$$

测试按 $K$ 的范围分布如下：

测试比例	$K$ 的范围
$14\%$	$1\le K\le 10$
$20\%$	$10\le K\le 100$
$32\%$	$100\le K\le 1000$
$20\%$	$1000\le K\le 10000$
$14\%$	$10000\le K\le 100000$

示例通信

编号	你的程序动作	评测程序动作或返回
1		biggest(4, 2)
2	compare(1, 2)	1
3	compare(1, 3)
4	compare(1, 4)
5	compare(2, 3)	3
6	compare(3, 4)
7	return {1, 3}

示例解释

隐藏排列为：

$$[4,1,3,2]$$

程序总共使用了 $5$ 次询问。若作者程序使用了 $4$ 次询问，则本测试点得到 $\frac{2}{3}$ 的分数。

具体地：

$$\text{yourScore}=5-(4-1)=2$$ $$\text{authorScore}=4-(4-1)=1$$

因此比例为：

$$\frac{\text{authorScore}+1}{\text{yourScore}+1}=\frac{1+1}{2+1}=\frac{2}{3}$$

本地测试

题目提供 biggest.h 和 Lgrader.cpp，可以与选手程序一起编译，在本地测试。

运行程序时，需要输入 $N$、$K$ 和测试类型。若测试类型为 0，则接下来手动输入排列；否则需要输入用于生成排列的随机种子。

@下发文件