题目背景

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

提示

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.