QOJ.ac

QOJ

Memory Limit: 1024 MB Total points: 100 Communication

# 4912. WereYouLast

统计

提示:在 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 存储单元,它们的编号为 $m1,2,\cdots ,m$ , 初始时的值为 False。你的程序可以调用如下函数:

  • bool query(int pos) : 该函数会返回第 pos 个存储单元的值。
  • void modify(int pos,bool v) : 该函数会将第 pos 个存储单元的值修改为 v。

记在第 $i$ 次调用中,你的程序的 query/modify 操作影响到了 $cnt_i$ 个不同的位置,你需要最小化

$C_1 = \max\limits_{i=1}^n cnt_i$ , 在某些测试点中,最小化 $C_2 = \max\limits_{i=2}^n cnt_i$ 也可以获得一定的分值。

注意:你的程序不能以任何自定义的形式在多次调用之间交换信息,这些被禁止的形式 包括但不限于使用全局变量(允许当常量用的全局变量(即,你没有通过修改全局变量来传递信息)),或是含有 static 关键词的变量。禁止任意形式的攻击交互库,这些被禁止的形式包括但不限于 修改交互库中的全局变量,或者在代码中使用主函数。得分程序可能会被人工检查,选手也可以对进行被禁止行为的程序进行申诉,若行为属实,将取消对应程序在本题的成绩。

注意:为了防止过度卡评测,在一次 WereYouLast 的调用中,你不能对同一个位置进行多于 $5$ 次的 query 或者 多于 $5$ 次的 modify ,如果在一次 WereYouLast 的调用中你的程序对一个位置调用了多于 5 次的 query 或者 多于 5 次的 modify , 超出上限的操作将会被判为 Invalid Operation , 你的程序会被判为 Wrong Answer.

输入格式

可执行文件从标准输入中读取数据。

输入包含一行两个整数 n,mn,m 表示程序调用次数,和全局存储单元的个数。

如何测试你的程序

下发文件中包含一个参考程序 sample.cpp

下发样例交互库 grader.cpp,设你的代码叫做 code.cpp 你可以采用如下命令进行编译:

g++ code.cpp -o code grader.cpp -O2 -std=c++11

你不能通过更改交互库得分。

你可以认为,最终测试的交互库与样例交互库的运行时间相差在 0.1s 以内,空间限制相差在 5MB 以内。

评分标准

每个测试点有固定的 $n$ $m$ 和若干个评分参数 $a_1, a_2, \cdots, a_{10}$ .

如果你的程序不能正确地完成任务,你将得到 $0$ 分。

在完成任务的基础上,

在测试点 $1$ 中, $C_1$ 每 $\leq$ 一个评分参数就会得到 $1$ 分。

在测试点 $2$ 中, $C_1$ 每 $\leq$ 一个评分参数就会得到 $1$ 分,$C_2$ 每 $\leq$ 一个评分参数就会得到 $1$ 分。

在测试点 $3$ 中, $C_1$ 每 $\leq$ 一个评分参数就会得到 $2$ 分,$C_2$ 每 $\leq$ 一个评分参数就会得到 $1$ 分。

在测试点 $4$ 中, $C_1$ 每 $\leq$ 一个评分参数就会得到 $2$ 分,$C_2$ 每 $\leq$ 一个评分参数就会得到 $2$ 分。

时间限制:见表格。

空间限制:1024 MB。

测试点编号 测试点总分 $n$ $m$ $a_1$ $a_2$ $a_3$ $a_4$ $a_5$ $a_6$ $a_7$ $a_8$ $a_9$ $a_{10}$ 时间限制
$1$ $10$ $= 2^{10}$ $=10$ $10$ $10$ $10$ $10$ $10$ $10$ $10$ $10$ $10$ $10$ 3s
$2$ $20$ $= 2^{16}$ $=10^5$ $14$ $13$ $12$ $11$ $9$ $8$ $7$ $6$ $6$ 4s
$3$ $30$ $= 2^{20}$ 5s
$4$ $40$ $= 2^{26}$ 14s