Description

Implement $\operatorname{remember}()$ and $\operatorname{compare}()$ to minimize the total number of memory accesses ($\operatorname{bit\_set}()$ and $\operatorname{bit\_get}()$) in the worst-case for all possible values of $a$ and $b$.

Your solution will be evaluated exhaustively:

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

Description of implementation

Actually many things are here. BUT, If YOU ARE GOING TO SUBMIT ON LUOGU, You Should Use C++, YOUR CODE MUSTN'T INCLUDE cmp.h.

Here is an example code to submit on Luogu.

#include<bits/stdc++.h>
using namespace std;
// Your codes here
extern"C" void bit_set(int);
extern"C" int bit_get(int);
extern"C" void remember(int a){
    // Your codes here
}
extern"C" int compare(int b){
    // Your codes here
}

Constraints

• You may be disqualified for any attempt to interact with the memory of our grading code.
• If your solution does not obey the protocol defined above (e.g. calling $\operatorname{bit\_set}()$ during $\operatorname{compare}()$ or with an invalid address), you will receive zero points.
• Time limit: your implementation must execute $4096$ calls to $\operatorname{remember}()$ and $4096\times 4096$ calls to $\operatorname{compare}()$ in under $10$ seconds.

From Balkan Olympiad in Informatics 2011 Day 2 T1 cmp.