#1829. 解谜游戏

    ID: 1829 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及- 上传者: 标签>CTT赛事:contest1788来源:qoj.ac数据:公开样例二分排序

解谜游戏

解谜游戏

题目描述

标题: 解谜游戏 - Problem - QOJ.ac

#8952. 解谜游戏

Statistics

The problem was used in the following contests:

这是一道交互题。

题目描述

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

你手中有 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 函数调用之前答案排列就已经确定,不会根据你的询问而变化。

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
1 0 2
Correct.
cnt = 3