QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 8952. 解谜游戏

Statistics

这是一道交互题。

题目描述

你迷上了一个解谜游戏。在游戏的这一关中,你的任务是打开一个宝箱。

你手中有 n 把钥匙,编号为 0n1;宝箱上有 n 个凹槽,编号也为 0n1。你的任务是收集相关线索,将钥匙按特定的顺序顺序插入凹槽,然后按动开关打开宝箱。这个正确的钥匙顺序可以视为一个长度为 n排列 p(下标从 0 开始)代表 i 号凹槽中应当放入 pi 号钥匙。

你的尝试可以视为给出一个长度为 n 的排列 q,表示在 i 号凹槽中放入 qi 号钥匙。如果对于每个 0in1 均有 pi=qi,则说明你的尝试是正确的,你将打开宝箱并顺利通关,否则通关失败。你只有一次尝试机会,因此你务必格外谨慎。

经过仔细地观察,你发现了这个宝箱的奥秘所在:宝箱的后面有一个隐藏的按钮。当你给出一个排列 q 并相应地将钥匙放入凹槽之后,你可以按动隐藏按钮,宝箱将给出有多少把钥匙放置的位置是正确的——即有多少个 0in1 满足 pi=qi。将你的这一操作称为一次询问,你可以在按下最终的开箱开关之前,多次改变你的排列 q 并进行询问,直到你收集到足够的信息能确定答案排列 p 为止。

但出于游戏难度和趣味性的考虑,还有一条特殊规定:你向宝箱询问的次数不得超过 20000 次,一旦超过,宝箱将立刻永久上锁,也就意味着你的游戏失败。能不能取得游戏的成功,就看你的本事了!

实现细节

你不需要,也不应该实现主函数。你需要在程序开头添加 #include "puzzle.h" 并实现如下函数:

void play(int n);
  • 其中,n 表示排列长度。
  • 交互库运行过程中,该函数将会被调用恰好一次。

你可以调用以下两个函数:

int query(const std::vector<int> &q);
  • 其中, q 应当是一个长度为 n 的排列,即 q 的长度应当为 n ,且 0n1 中的所有整数在 q0qn1 中均恰好出现一次。

  • 函数将比较你给出的排列 q 与答案排列 p,并返回本次询问的结果,即有多少个整数 i 满足 0in1pi=qi

  • 你调用该函数的次数不应当超过 20000
void check(const std::vector<int> &q);
  • 其中, q 应当是一个长度为 n 的排列,即 q 的大小应当为 n ,且 0n1 中的所有整数在 q0qn1 中均恰好出现一次。
  • 这个函数应当在你的程序运行 play 函数时恰好被执行一次。
  • 函数将比较你给出的排列 q 与答案排列 p,如果 p=q 则认为你给出的答案正确,否则认为你给出的答案错误。
  • 无论如何,交互库将在执行完该函数后,输出相应信息并立即终止运行。

你应当保证调用 querycheck 函数时传入的参数符合上述要求。

你可以查看下发文件中的参考交互库了解更多实现细节。

测试程序方式

下发文件中提供了交互库的参考实现 grader.cpp最终测试时所用的交互库实现与该实现有不同,因此选手的解法不应依赖交互库实现。

假设你的源程序名为 puzzle.cpp,你需要将下发文件放入源程序所在的目录中,并在目录下使用如下命令编译得到可执行程序:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm

运行按上述方法编译得到的可执行文件时:

  • 可执行文件将从标准输入读入以下格式的数据:

    • 第一行:一个正整数 n,表示排列长度。你需要保证 2n1000
    • 第二行: n 个整数 p0,p1,,pn1,表示答案排列。你需要保证 p0,,pn1 是一个长度为 n 的排列,即 0n1 中的所有整数均恰好出现一次。
  • 读入完成之后,交互库将用该组数据进行测试,并输出如下内容:

    • 如果你的程序正常运行,调用 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 分。否则,该测试点的得分将由下述“子任务”中的描述给出。

子任务

本题使用捆绑测试。对于每个子任务而言,你的得分是子任务中所有测试点得分的最小值。

对于所有测试点,1n1000

子任务编号分值 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<m20000 25m14000400
9500<m14000 50m9500300
m9500 60

注意事项

保证对于任何合法的数据及在限制范围内的调用,交互库本身运行所用的时间不会超过 0.2s,运行所用的空间不会超过 128MiB

交互库正常运行需包含的头文件已经在下发的参考交互库中给出,你的程序可以包含你需要的头文件。

本题的交互库不是自适应的,即在 play 函数调用之前答案排列就已经确定,不会根据你的询问而变化。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为,所得分数无效。