loj#P6775. 「2021 营员交流」枇配
「2021 营员交流」枇配
题目描述
一年一度的综艺节目《中国新毒瘤》又开始了。zrsrm 从小就梦想成为一名工程师。本季度的的导师将会带领大家学会毒瘤。
轻车熟路的 zrsrm 顺利地通过了海选,接下来的环节是导师 34221-xhy 的面试,面试题是这样的:
- 在大前年的赛场上,有 名选手,他们将在一轮的筛选环节中进行 场比赛,每场比赛有两个人参加,而每个人恰好参加了一场比赛。
- 现在,这 名选手站成了一排,你的任务则是找出每位选手的对手。为了方便,我们将选手从 到 编号。
当然,早已忘记大前年的比赛内容的 zrsrm 答不出这道题,于是导师 34221-xhy 允许 zrsrm 询问他若干个问题,每个问题必须是这个格式:
- 第 个选手到第 个选手中,可以找到多少对选手参加了同一场比赛。
当然,导师 34221-xhy 对 zrsrm 的评价和他询问的次数有关,询问次数越少评价越高,你可以帮帮他吗?
任务
你需要编写一个函数,以完成题目的任务:
match(n)
:- 表示共有 场比赛;
- 你需要返回一个大小为 的
std::vector
,其中第 个元素表示编号为 的人的对手编号。
你可以调用函数 query 以帮助你确定每个数的值。
query(l, r)
:- 分别表示你询问的区间的左右端点;
- 如果询问次数已经超过 3000000,成绩立刻将记为零分;
- 如果 或者 ,将会报错(成绩记为零分),否则会返回询问的结果。
实现细节
本题只支持 C++ 以及以上版本。
你只能提交一个源文件实现如上所述的 match
函数,并且遵循下面的命名和接口。你需要包含头文件 match.h
。
std::vector<int> match(int n);
int query(int l, int r);
如果有不清楚的地方,见样例及测评库下载,内附了样例程序。
输入格式
评测系统将读入如下格式的输入数据:
第一行一个正整数 。
接下来一行共 个整数,表示每个人的对手的编号,其中第 个数表示第 个人的对手编号。
输出格式
评测系统将输出一个整数,表示询问的次数
5
1 0 3 2 5 4 7 6 9 8
0
数据范围与提示
共两个子任务,满分分数分别为 分、 分。
对于每一个测试点,评测机会使用 个评分参数 计算你的成绩,保证 。
计算方法如下:
- 若你的询问次数为 ,则你在该测试点的得分百分比 ,百分比乘以该测试点所在子任务满分分数即为该测试点得分;
- 一个子任务的实际得分为该子任务内所有测试点得分的最小值。
具体的评分参数如下:
对于第一个子任务:。
对于第二个子任务:。
保证交互库的用时不会超过 ,使用的内存空间不会超过 。