题目背景

这是一道 Grader 交互题。

本题时限 10s，空限除交互库所用内存仅 16MB。

本题分数最高 $190$，但标解所选择的方案可得 $100$ 分。

测评注意事项

• 你的代码中不应包含 cmp.h，而应该在开头包含下面两个函数的声明：
  • void bit_set(int);
  • int bit_get(int);
• 你的代码中应该实现两个函数 ：
  • void remember(int a);
  • int compare(int b);

换句话说，您可以在如下的代码模板中编写程序：

#include <bits/stdc++.h>
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$ 未知：
  • 若 $b<a$，请返回 $-1$。
  • 若 $b=a$，请返回 $0$。
  • 若 $b>a$，请返回 $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 Day 2 T1 cmp。

感谢

交互库。