#2035. WereYouLast
WereYouLast
WereYouLast
题目描述
标题: WereYouLast - Problem - QOJ.ac
#4912. WereYouLast
The problem was used in the following contests:
**提示:**在 QOJ 中评测时,为了检查你是否使用了全局变量,你的程序可能被运行在若干个(至多 4 个)不同的进程中,每次将选择一个进程调用对应的 WereYouLast,不同进程间不能共享全局变量。本题的时间限制(14 秒)指你在所有进程中使用的时间之和,空间限制(1024 MB)指你在每个进程中使用的空间的最大值。
题意更新:T3中“影响”是指,只要某个位置被query或者modify了那么就算被影响了;禁止在WereYouLast中递归调用自己.
特别提醒:由于编译上的问题,请在你的代码前加入如下声明:
bool query(int);
void modify(int,bool);
题目描述
这是一道交互题。
在本题中,**你不需要实现主函数。**你需要实现一个函数
bool WereYouLast(int n,int m)
这个函数会被调用恰好 n 次,你需要正确地返回这是否是最后一次调用。
交互库会为你的程序提供 m 个全局 bool 存储单元,它们的编号为 1,2,⋯,m , 初始时的值为 False。你的程序可以调用如下函数:
bool query(int pos): 该函数会返回第pos个存储单元的值。void modify(int pos,bool v): 该函数会将第pos个存储单元的值修改为 v。
记在第 i 次调用中,你的程序的 query/modify 操作影响到了 cnti 个不同的位置,你需要最小化
C1=maxi=1ncnti , 在某些测试点中,最小化 C2=maxi=2ncnti 也可以获得一定的分值。
注意:你的程序不能以任何自定义的形式在多次调用之间交换信息,这些被禁止的形式 包括但不限于使用全局变量(允许当常量用的全局变量(即,你没有通过修改全局变量来传递信息)),或是含有 static 关键词的变量。**禁止任意形式的攻击交互库,**这些被禁止的形式包括但不限于 修改交互库中的全局变量,或者在代码中使用主函数。得分程序可能会被人工检查,选手也可以对进行被禁止行为的程序进行申诉,若行为属实,将取消对应程序在本题的成绩。
注意:为了防止过度卡评测,在一次 WereYouLast 的调用中,你不能对同一个位置进行多于 5 次的 query 或者 多于 5 次的 modify ,如果在一次 WereYouLast 的调用中你的程序对一个位置调用了多于 5 次的 query 或者 多于 5 次的 modify , 超出上限的操作将会被判为 Invalid Operation , 你的程序会被判为 Wrong Answer.
输入格式
可执行文件从标准输入中读取数据。
输入包含一行两个整数 n,m 表示程序调用次数,和全局存储单元的个数。
如何测试你的程序
下发文件中包含一个参考程序 sample.cpp。
下发样例交互库 grader.cpp,设你的代码叫做 code.cpp 你可以采用如下命令进行编译:
g++ code.cpp -o code grader.cpp -O2 -std=c++11
你不能通过更改交互库得分。
你可以认为,最终测试的交互库与样例交互库的运行时间相差在 0.1s 以内,空间限制相差在 5MB 以内。
评分标准
每个测试点有固定的 n m 和若干个评分参数 a1,a2,⋯,a10 .
如果你的程序不能正确地完成任务,你将得到 0 分。
在完成任务的基础上,
在测试点 1 中, C1 每 ≤ 一个评分参数就会得到 1 分。
在测试点 2 中, C1 每 ≤ 一个评分参数就会得到 1 分,C2 每 ≤ 一个评分参数就会得到 1 分。
在测试点 3 中, C1 每 ≤ 一个评分参数就会得到 2 分,C2 每 ≤ 一个评分参数就会得到 1 分。
在测试点 4 中, C1 每 ≤ 一个评分参数就会得到 2 分,C2 每 ≤ 一个评分参数就会得到 2 分。
时间限制:见表格。
空间限制:1024 MB。
测试点编号 测试点总分 n m a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 时间限制 1 10 =210 =10 10 10 10 10 10 10 10 10 10 10 3s 2 20 =216 =105 14 13 12 11 9 8 7 6 6 4s 3 30 =220 5s 4 40 =226 14s
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1024 10
10 10 10 10 10 10 10 10 10 10
1 0
样例 2
65536 100000
15 14 13 12 11 10 9 8 7 6
1 1