P6752 [BalkanOI 2011] cmp

这是一道 **Grader 交互题**。 本题时限 10s，空限除交互库所用内存仅 16MB。 本题分数最高 $190$，但标解所选择的方案可得 $100$ 分。 #### 测评注意事项 - 你的代码中不应包含 `cmp.h`，而应该在开头包含下面两个函数的声明： - `void bit_set(int);` - `int bit_get(int);` - 你的代码中应该实现两个函数 ： - `void remember(int a);` - `int compare(int b);` 换句话说，您可以在如下的代码模板中编写程序： ```cpp #include using namespace std; do something... extern "C" void bit_set(int); extern "C" int bit_get(int); extern "C" void remember(int a) { do something... } extern "C" int compare(int b) { do something... } ```

我们有一个第一维长度为 $4096$，第二维长度为 $10240$ 的二维 $01$ 数组 $mem$，初始时所有值为 $0$。 您需要编写在 $01$ 数组上执行的两个操作 `void remember(int a)` 和 `int compare(int b)`。 #### 实现细节 `void remember(int a)` ： - 保证 $0\le a\le 4095$。 - 您可以调用 `void bit_set(int ad)`，其中您需要保证 $1\le ad \le 10240$。 - 这会导致 $mem_{a,ad}=1$。 `int compare(int b)`： - 保证 $0\le b\le 4095$。 - 您需要将 $a$ 与 $b$ 进行比较，其中 $a$ 未知： - 若 $ba$，请返回 $1$。 - 您可以调用 `int bit_get(int ad)`，其中您需要保证 $1\le ad \le 10240$。 - 这会返回 $mem_{a,ad}$ 的值 #### 任务 您应该实现上述两个函数 `void remember(int a)` 和 `int compare(int b)` 在最大程度上减少 `void bit_set(int ad)` 和 `int bit_get(int ad)` 的调用次数。 您的得分由以下伪代码计算： ``` define AllMemory = array [0..4095][1..10240] of bits set AllMemory to zeros for a = 0..4095: define bit_set(address): AllMemory[a][address] = 1 remember(a) let maxA= the maximum number of bit_set() calls executed for any a for (a,b) ∈ {0..4095}×{0..4095} in random order (i.e. all valid pairs (a,b) are considered, in some random order) define bit_get(address): return AllMemory[a][address] answer =compare(b) if answer for comparing a and b is incorrect : your score = 0; exit let maxB = the maximum number of bit_get() calls executed for any (a,b) pair T=maxA + maxB If (T>20): your score = 0; exit else your score = 1 + 9 * (21– T); exit ```

无

无

#### 限制 - 如果您的解决方案不遵守上面的实现细节部分，您保龄。 - 您的解决方案必须可以在 10s 内调用 $4096$ 次 `void remember(int a)` 和 $4096\times 4096$ 次 `int compare(int b)`。 #### 说明 本题译自 [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 2](http://www.boi2011.ro/boi2011/?pagina=probleme) [T1 cmp](http://www.boi2011.ro/resurse/tasks/cmp.zip)。 感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的交互库。