P6752 [BalkanOI 2011] cmp

You must design an algorithm for an ancient computer whose memory is just an array of $10240$ bits.The memory is initialized to zero, after which you may write and read a single bit at a time. You must implement two operations on this computer: $\operatorname{remember}(a)$: $a$ is an integer between $0$ and $4095$ - The implementation of this operation may call: - - $\operatorname{bit\_set}(address)$: $\ \ \ \ $ $address$ is an integer between $1$ and $10240$ - - The memory bit at position address will be set to $1$ $\operatorname{compare}(b)$: $b$ is an integer between $0$ and $4095$ - if $b < a$, it should return $-1$ - if $b = a$, it should return $0$ - if $b > a$, it should return $1$ - The implementation of this operation may call: - - $\operatorname{bit\_get}(address)$ Returns the memory bit at position $address$: $1$ if it was set through $\operatorname{bit\_set}()$ during the $\operatorname{remember}(a)$ operation, and $0$ otherwise.

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 ```

N/A

N/A

### 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.** ```cpp #include 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](http://www.boi2011.ro/boi2011/) [Day 2](http://www.boi2011.ro/boi2011/?pagina=probleme) [T1 cmp](http://www.boi2011.ro/resurse/tasks/cmp.zip).