这是一道交互题。
题目描述
你迷上了一个解谜游戏。在游戏的这一关中,你的任务是打开一个宝箱。
你手中有 n 把钥匙,编号为 0∼n−1;宝箱上有 n 个凹槽,编号也为 0∼n−1。你的任务是收集相关线索,将钥匙按特定的顺序顺序插入凹槽,然后按动开关打开宝箱。这个正确的钥匙顺序可以视为一个长度为 n 的排列 p(下标从 0 开始)代表 i 号凹槽中应当放入 pi 号钥匙。
你的尝试可以视为给出一个长度为 n 的排列 q,表示在 i 号凹槽中放入 qi 号钥匙。如果对于每个 0≤i≤n−1 均有 pi=qi,则说明你的尝试是正确的,你将打开宝箱并顺利通关,否则通关失败。你只有一次尝试机会,因此你务必格外谨慎。
经过仔细地观察,你发现了这个宝箱的奥秘所在:宝箱的后面有一个隐藏的按钮。当你给出一个排列 q 并相应地将钥匙放入凹槽之后,你可以按动隐藏按钮,宝箱将给出有多少把钥匙放置的位置是正确的——即有多少个 0≤i≤n−1 满足 pi=qi。将你的这一操作称为一次询问,你可以在按下最终的开箱开关之前,多次改变你的排列 q 并进行询问,直到你收集到足够的信息能确定答案排列 p 为止。
但出于游戏难度和趣味性的考虑,还有一条特殊规定:你向宝箱询问的次数不得超过 20000 次,一旦超过,宝箱将立刻永久上锁,也就意味着你的游戏失败。能不能取得游戏的成功,就看你的本事了!
实现细节
你不需要,也不应该实现主函数。你需要在程序开头添加 #include "puzzle.h"
并实现如下函数:
void play(int n);
- 其中,n 表示排列长度。
- 交互库运行过程中,该函数将会被调用恰好一次。
你可以调用以下两个函数:
int query(const std::vector<int> &q);
其中, q 应当是一个长度为 n 的排列,即 q 的长度应当为 n ,且 0∼n−1 中的所有整数在 q0∼qn−1 中均恰好出现一次。
函数将比较你给出的排列 q 与答案排列 p,并返回本次询问的结果,即有多少个整数 i 满足 0≤i≤n−1 且 pi=qi。
- 你调用该函数的次数不应当超过 20000。
void check(const std::vector<int> &q);
- 其中, q 应当是一个长度为 n 的排列,即 q 的大小应当为 n ,且 0∼n−1 中的所有整数在 q0∼qn−1 中均恰好出现一次。
- 这个函数应当在你的程序运行
play
函数时恰好被执行一次。 - 函数将比较你给出的排列 q 与答案排列 p,如果 p=q 则认为你给出的答案正确,否则认为你给出的答案错误。
- 无论如何,交互库将在执行完该函数后,输出相应信息并立即终止运行。
你应当保证调用 query
或 check
函数时传入的参数符合上述要求。
你可以查看下发文件中的参考交互库了解更多实现细节。
测试程序方式
下发文件中提供了交互库的参考实现 grader.cpp
。最终测试时所用的交互库实现与该实现有不同,因此选手的解法不应依赖交互库实现。
假设你的源程序名为 puzzle.cpp
,你需要将下发文件放入源程序所在的目录中,并在目录下使用如下命令编译得到可执行程序:
g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm
运行按上述方法编译得到的可执行文件时:
可执行文件将从标准输入读入以下格式的数据:
- 第一行:一个正整数 n,表示排列长度。你需要保证 2≤n≤1000;
- 第二行: n 个整数 p0,p1,⋯,pn−1,表示答案排列。你需要保证 p0,⋯,pn−1 是一个长度为 n 的排列,即 0∼n−1 中的所有整数均恰好出现一次。
读入完成之后,交互库将用该组数据进行测试,并输出如下内容:
如果你的程序正常运行,调用
query
函数的次数不超过 20000,并在调用check
函数时传入了正确的排列,则会输出以下内容:Correct. cnt = x
其中 x 为你的程序调用
query
函数的次数。否则,将会输出相应的错误信息。
样例
输入
3
1 0 2
输出
Correct.
cnt = 3
解释
这是使用下发的 grader.cpp
和能够正确运行的源程序得到的可能输出文件。
对于此样例,一种可能的调用方式为:
- 调用
query([0, 1, 2])
,返回 1; - 调用
query([0, 2, 1])
,返回 0; - 调用
query([1, 0, 2])
,返回 3; - 调用
check([1, 0, 2])
。
评分方式
评测时,你只需在 OJ 上提交你的源程序,修改下发的其他文件不会对评测结果产生影响。
本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得 0 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。
在上述条件以外,在一个测试点中,若你的程序执行了非法的函数调用、没有调用 check
函数或 check
函数给出了错误回答、或调用 query
函数的次数超过 20000,该测试点将会获得 0 分。否则,该测试点的得分将由下述“子任务”中的描述给出。
子任务
本题使用捆绑测试。对于每个子任务而言,你的得分是子任务中所有测试点得分的最小值。
对于所有测试点,1≤n≤1000。
子任务编号 | 分值 | n≤ |
---|---|---|
1 | 2 | 5 |
2 | 4 | 10 |
3 | 6 | 30 |
4 | 8 | 100 |
5 | 10 | 300 |
6 | 500 | |
7 | 60 | 1000 |
对于前 6 个子任务,如果你的程序正常运行,调用 query
函数的次数不超过 20000,并在调用 check
函数时传入了正确的排列,则可以获得该测试点的满分。
对于第 7 个子任务,你的程序在上述基础之上还可能获得部分分。设你的程序调用 query
的次数为 m,则你的得分如下:
条件 | 得分 |
---|---|
m>20000 | 0 |
14000<m≤20000 | 25−m−14000400 |
9500<m≤14000 | 50−m−9500300 |
m≤9500 | 60 |
注意事项
保证对于任何合法的数据及在限制范围内的调用,交互库本身运行所用的时间不会超过 0.2s,运行所用的空间不会超过 128MiB。
交互库正常运行需包含的头文件已经在下发的参考交互库中给出,你的程序可以包含你需要的头文件。
本题的交互库不是自适应的,即在 play
函数调用之前答案排列就已经确定,不会根据你的询问而变化。
通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为,所得分数无效。