loj#P6775. 「2021 营员交流」枇配

「2021 营员交流」枇配

题目描述

一年一度的综艺节目《中国新毒瘤》又开始了。zrsrm 从小就梦想成为一名工程师。本季度的的导师将会带领大家学会毒瘤。


轻车熟路的 zrsrm 顺利地通过了海选,接下来的环节是导师 34221-xhy 的面试,面试题是这样的:

  • 在大前年的赛场上,有 2n2n 名选手,他们将在一轮的筛选环节中进行 nn 场比赛,每场比赛有两个人参加,而每个人恰好参加了一场比赛。
  • 现在,这 2n2n 名选手站成了一排,你的任务则是找出每位选手的对手。为了方便,我们将选手从 002n12n-1 编号。

当然,早已忘记大前年的比赛内容的 zrsrm 答不出这道题,于是导师 34221-xhy 允许 zrsrm 询问他若干个问题,每个问题必须是这个格式:

  • ll 个选手到第 rr 个选手中,可以找到多少对选手参加了同一场比赛。

当然,导师 34221-xhy 对 zrsrm 的评价和他询问的次数有关,询问次数越少评价越高,你可以帮帮他吗?

任务

你需要编写一个函数,以完成题目的任务:

  • match(n):
    • nn 表示共有 nn 场比赛;
    • 你需要返回一个大小为 2n2nstd::vector,其中第 i+1i + 1 个元素表示编号为 ii 的人的对手编号。

你可以调用函数 query 以帮助你确定每个数的值。

  • query(l, r):
    • l,rl, r 分别表示你询问的区间的左右端点;
    • 如果询问次数已经超过 3000000,成绩立刻将记为零分;
    • 如果 [l,r]⊈[0,2n)[l, r] \not \subseteq [0, 2n) 或者 l>rl > r,将会报错(成绩记为零分),否则会返回询问的结果。

实现细节

本题只支持 C++ 以及以上版本。

你只能提交一个源文件实现如上所述的 match 函数,并且遵循下面的命名和接口。你需要包含头文件 match.h

std::vector<int> match(int n);
int query(int l, int r);

如果有不清楚的地方,见样例及测评库下载,内附了样例程序。

输入格式

评测系统将读入如下格式的输入数据:

第一行一个正整数 nn

接下来一行共 2n2n 个整数,表示每个人的对手的编号,其中第 i+1i + 1 个数表示第 ii 个人的对手编号。

输出格式

评测系统将输出一个整数,表示询问的次数

5
1 0 3 2 5 4 7 6 9 8

0

数据范围与提示

共两个子任务,满分分数分别为 4040 分、6060 分。

对于每一个测试点,评测机会使用 2525 个评分参数 ω1,ω2,,ω25\omega_1,\omega_2,\ldots,\omega_{25} 计算你的成绩,保证 ωiωi+1\omega_i\geq\omega_{i+1}

计算方法如下:

  • 若你的询问次数为 TT,则你在该测试点的得分百分比 p=max{x  Tωx}×4%p = \max\{x~|~T\leq \omega_x\}\times 4\%,百分比乘以该测试点所在子任务满分分数即为该测试点得分;
  • 一个子任务的实际得分为该子任务内所有测试点得分的最小值。

具体的评分参数如下:

ii ωi\omega_i ii ωi\omega_i ii ωi\omega_i ii ωi\omega_i ii ωi\omega_i
11 30000003000000 66 20000002000000 1111 17900001790000 1616 17100001710000 2121 16700001670000
22 30000003000000 77 19000001900000 1212 17700001770000 1717 17000001700000 2222 16650001665000
33 20000002000000 88 18500001850000 1313 17500001750000 1818 16900001690000 2323 16600001660000
44 20000002000000 99 18300001830000 1414 17300001730000 1919 16800001680000 2424 16550001655000
55 20000002000000 1010 18000001800000 1515 17200001720000 2020 16750001675000 2525 16500001650000

对于第一个子任务:n=1000n = 1000

对于第二个子任务:n=100000n = 100000

保证交互库的用时不会超过 1s1\texttt{s},使用的内存空间不会超过 256MB256\texttt{MB}