#P11266. 鱼和熊掌不可兼得

鱼和熊掌不可兼得

这是一道交互题,且只支持c++语言。

下发文件如下 下发文件

众所周知,胖头鱼是一种嗜睡的生物。

胖头鱼终于醒来了,不过他发现班主任语文老师正在上语文课,于是下课之后他被请去办公室喝茶。

语文老师想让胖头鱼默写《鱼我所欲也》作为惩罚,胖头鱼心中万马奔腾,因为他的语文书连名字都没有写。

语文老师决定给胖头鱼一点提示,文言文可以被看作一个1n1-n的排列pp,胖头鱼完全不知道文言文的内容,但他每次可以写出一个1n1-n的排列qq作为询问,班主任会告诉胖头鱼他的询问里有多少个位置上的数是对的,即i=1n[p[i]=q[i]]\sum_{i=1}^n[p[i]=q[i]],在有限次询问内,最后胖头鱼需要默写出正确的文言文p。

胖头鱼想要早点完成这个”默写“,以吃完午饭后继续睡觉,然而刚睡醒的胖头鱼实在是无法思考,他希望你能帮帮他。

任务介绍:

你需要实现一个函数 guess,以帮助胖头鱼完成“默写”。

guess(n, limit)

  • n为排列的长度。
  • limit为你最多可以询问的次数。
  • 该函数的返回值是一个std :: vector<int>,表示你提交的排列。

在每个测试点中,交互库都会调用恰好一次 guess 函数。

你可以调用函数count(q)来询问老师:

count(std :: vector<int> q)

  • q表示你询问的排列。
  • 这个函数会返回询问的排列与答案的排列有多少个位置是相同的。

std :: vector<int> p存储一个1n1-n的排列的格式如下:

  • p.size()=n
  • 排列的第ii个位置的数是p[i-1]

在函数guess返回之后,交互库会检查返回的结果,只有完全正确才算完成“默写”。

实现方法

你需要且只能提交一个源文件 game.cpp 实现上述函数,且遵循下面的命名和接口:

源代码中需要包含头文件 game.h。

你需要实现的函数guess

std :: vector<int> guess(int n, int limit);

函数count的接口信息如下:

int count(std :: vector<int> c);

如何测试你的程序

你需要在本题目录下使用如下命令编译得到可执行程序:

g++ game.cpp grader.cpp -o game -O2

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

第一行两个整数nnlimitlimit,需要保证1<=n<=5000,1<=limit<=23111<=n<=5000,1<=limit<=2^{31}-1

第二行nn个整数p[i]p[i],需要保证pp是一个1n1-n的排列。

读入完成之后,交互库将调用 guess 函数。如果此时你调用 count 的次数超过 limitlimit 次,则交互库会输出详细的错误信息,并退出。

接下来交互库会判断游戏目标是否完成。如果完成,则会输出 "Accepted.",否则会输出相应的错误信息。

如果传入 count 函数的参数非法(不是一个1n1-n的排列),那么交互库会输出对应的错误信息,并退出。

如果要使用自己的输入文件进行测试,请保证输入文件符合以上格式要求,否则不保证程序能正确运行。

如何使用样例源代码

下发文件中,有样例源代码 game_sample.cpp,将其复制为 game.cpp,再把grader.cpp和game.h也复制到同一个目录下,按照上文中提到的方式进行编译,即能通过编译得到可执行程序。

接下来你需要修改game.cpp这个文件的实现,以达到题目的要求。

样例

input

5 1000000

1 2 3 4 5

output

Accpeted. You use 0 queries

评分方式

只有以下三个条件都满足的情况下,该测试点得满分,否则该测试点得 0 分:

  1. 程序在时间限制和空间限制下正常运行。
  2. 调用count的次数不超过limitlimit
  3. guess返回的是正确答案。

题目中所给的时间、空间限制为你的代码和交互库加起来可以使用的时间和空间,评测时的交互库和下发的相似但不相同,请选手自己注意交互库带来的时间和空间影响。

限制与约定

数据采用捆绑测试,你能获得一个子任务的分数当且仅当你通过了该子任务下的所有测试点。

对于所有数据,满足2<=n<=5000,1<=limit<=1062<=n<=5000,1<=limit<=10^6

子任务编号 00 11 22 33 44 55 66 77 88 99
n<=n<= 99 5050 100100 200200 500500 10001000 30003000 40004000 50005000
limit=limit= 10610^6 10510^5 21042*10^4 51045*10^4 2.71042.7*10^4 91049*10^4 5.21045.2*10^4 51045*10^4
分值 99 1515 88 77 88 1313 88 1616 88