这是一道交互题。

很遗憾这题并不支持C++以外的语言

小Q无聊的时候喜欢玩一个叫“大家来找茬”的游戏。

这个游戏的规则是这样的：在每一局游戏中，系统向玩家展示一组（两张）图，这两张图之间只有几处不同，玩家需要在规定时间内找出尽可能多的不同点。若玩家在时间用尽前找出了所有不同点，则称该局“挑战成功”，否则时间用尽时游戏结束，该局“挑战失败”。

最近，这个游戏推出了新模式——生存模式。在生存模式中，系统将准备 $m$ 组图片并依次展示给玩家，当系统展示某组图片时，玩家需要对它们“找茬”。在该模式中，游戏提供“下一图”按钮：玩家不需要将当前这组图片中的不同点全部找出便可以点击该按钮来处理下一张图。事实上，如果玩家不点击“下一图”按钮，即使玩家已经将当前图中的不同点全部找出，系统也不会自动切换到下一图。需要注意的是，一旦点击了“下一图”按钮，便再也无法回来处理当前图了。当规定时间用尽时，系统自动结束游戏。在该模式中，游戏的结果也从简单的成功/失败变成了分数：在一局中玩家的得分定义为该局规定时间内玩家正确找出的不同点数，找错、漏找均不扣分。

开启了一个新的模式，第一件事情自然是：刷分。作为一个计算机工程汪，小Q自然不会单纯到徒手刷分啦。利用技术手段对游戏程序进行分析后，小Q发现，该游戏在为玩家生成图片时使用了如下策略：首先准备两张大图，并记录下它们之间所有 $n$ 个不同点的位置；每次需要生成一组图片时，就从这两张大图中取一组对应的矩形区域。

具体来说，这两张大图被分别分成了 $U\times U$ 个小块，每个小块都有一个坐标 $(x,y)$，其中 $0\le x,y<U$。这些小块中有 $n$ 个小块是不同点，其余不是。每次需要生成一组图片时，系统生成两个坐标 $(x_1,y_1),(x_2,y_2)$ 其中 $x_1\le x_2,y_1\le y_2$，并将 $(x_1,y_1)-(x_2,y_2)$ 这个矩形区域作为本次生成的结果。

神通广大的小Q没多久就搞到了所有 $n$ 个不同点的坐标，并找到了截获每一组图片的坐标信息 $(x_1,y_1),(x_2,y_2)$ 的方法，于是剩下的事情就简单了：只需在 $n$ 个不同点中，找出那些在矩形 $(x_1,y_1)-(x_2,y_2)$ 里的点即可。善良的小Q为了与你分享刷分的快感，将这个简单的任务交给了你。

交互格式

你需要实现 spots.cpp。在该文件的开头，你应当使用 #include "spots.h" 来包含头文件 spots.h；接下来，你需要实现 spots_init 和 spots 两个函数。详细说明如下：

void spots_init(std::vector< std::pair<int, int> > points); 当小Q想要开始一局游戏之前，小Q会调用该函数。其参数 points 是一个 vector，存放有所有不同点的坐标。你应当在该函数内初始化你需要的数据。

void spots(int x1, int y1, int x2, int y2); 当系统给小Q一组新的图片 $(x_1,y_1)-(x_2,y_2)$ 时，小Q会调用该函数。四个参数的意义如上文所示。在该函数中，你需要尽可能多的找出该矩形区域内的不同点。你可以调用如下函数来报告你找到的不同点：

bool report(int x); 其中参数 x 表示你找到的不同点的编号。一个点的编号等于它在传入的 vector 中的下标。若该函数返回 true 则表示该不同点正确，否则表示该不同点有误。当你已经处理完该组图片时，应主动让 spots 函数返回。

需要特别说明的是，你不允许从标准输入或任何文件中读取任何信息，也不允许向标准输出或任何文件中输出任何信息。

选手目录下的 spots_sample.cpp 提供了 spots.cpp 的一个示例。

限制与约定

本题共有10个测试点，每个测试点的规模如下：

其中点数和一列表示所有询问区域中点数的总和。

对于每个测试点，我们将按如下方式进行评分：

首先，我们将调用你的 spots_init 函数。你将有 $1$ 秒的时间来完成初始化工作。如果你的 spots_init 函数在 $1$ 秒内没有返回，则该测试点得 $0$ 分。

之后，你有 $1$ 秒的时间来处理询问。我们将在这 $1$ 秒内不停地调用你的 spots 函数，直到时间用尽。如果在某次 report 时我们发现时间已经用尽，我们将直接计算分数并结束程序。请注意在该过程中对 report 函数的调用也会计入用时，但你可以认为 report 函数足够快，在 $1$ 秒内至少能够执行 ${10}^8$ 次。

请保证你的 spots 函数的每次调用能在 $1$ 秒内返回，否则该测试点可能被判为 0 分。

如果你的程序在任何时间点使用了超过 $512\mathtt{\text{MB}}$ 内存，则该测试点得 0 分。（注意交互库也是占内存的，你可以认为它使用的空间不超过$64\mathtt{\text{MB}}$）

如果你的程序没有发生上述任意一种得 $0$ 分的情况，我们将按如下规则对你的程序进行记分：设你的程序在 $1$ 秒内正确报告的结果数为 $\mathrm{UserCnt}$，我们的参考程序在1秒内正确报告的结果数为 $\mathrm{StdCnt}$，如果 $\mathrm{UserCnt}\ge \mathrm{StdCnt}$，则该测试点获得10分，否则该测试点的得分为

$$10\cdot \sqrt{\frac{\mathrm{UserCnt}}{\mathrm{StdCnt}}}$$

除上述限制外，本题还有总时间和空间限制（因为种种原因我们调小了时限，但是并不影响大家解题）：

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

但该时间限制仅为保证程序能够结束而设置，选手无需关心。

样例评分程序

在选手目录下提供了样例评分程序 grader.cpp。

该程序从标准输入中读取点和询问的信息，并与你的程序进行交互。读入信息的具体格式见下文。当程序运行结束时，将把结果打印在标准输出。

要使用该样例评分程序，你需要将它与你的 spots.cpp 一起编译。参考命令行如下：

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

需要指出的是，样例评分程序并没有提供测试时间的功能。

样例评分程序的评测方式

第一行包含两个整数 $n,m$。

接下来的 $n$ 行，每行包含两个整数 $x,y$，描述了一个不同点的坐标。

接下来的 $m$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，描述了一个询问。

例如：

5 3
1 1
2 2
3 3
4 4
5 5
0 0 1 3
2 2 3 3
10 10 11 12

最终评测方式

最终的测评库非常神秘，不会下发。比赛中途进行提交是使用最终的测评库测试样例，即第一组数据。

下载

相关文件下载