Description

我们有一个第一维长度为 $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

Hint

限制

• 如果您的解决方案不遵守上面的实现细节部分，您保龄。

• 您的解决方案必须可以在 10s 内调用 $4096$ 次 void remember(int a) 和 $4096\times 4096$ 次 int compare(int b)。

说明

本题译自 Balkan Olympiad in Informatics 2011 Day 2 T1 cmp。

感谢