#include "advisor.h"
#include <queue>
using namespace std;
const int INF = 1000000000;
queue<int> useWhen[100000];
queue<int> ret;
priority_queue<pair<int, int>> pq;
pair<int, int> shelf[100000]; int loc[100000];
bool use[100000], initial[100000], removable[100000];
void ComputeAdvice(int *C, int N, int K, int M) {
for(int i=0;i<N;i++) useWhen[C[i]].push(i);
for(int i=0;i<K;i++) {
shelf[i] = {i, -1}; use[i] = true; loc[i] = i;
if(useWhen[i].empty()) pq.push({INF, i});
else pq.push({useWhen[i].front(), i});
}
for(int i=0;i<N;i++){
if(!use[C[i]]){
int m = pq.top().second; pq.pop();
use[shelf[m].first] = false;
use[C[i]] = true;
loc[C[i]] = m;
shelf[m] = {C[i], i};
useWhen[C[i]].pop();
if(useWhen[C[i]].empty()) pq.push({INF, m});
else pq.push({useWhen[C[i]].front(), m});
}
else{
useWhen[C[i]].pop();
if(useWhen[C[i]].empty()) pq.push({INF, loc[C[i]]});
else pq.push({useWhen[C[i]].front(), loc[C[i]]});
if(shelf[loc[C[i]]].second != -1)
removable[shelf[loc[C[i]]].second] = true;
else
initial[C[i]] = true;
shelf[loc[C[i]]].second = i;
}
}
for(int i=0;i<K;i++){
WriteAdvice(initial[i]);
}
for(int i=0;i<N;i++){
WriteAdvice(removable[i]);
}
}
#include "assistant.h"
#include <queue>
std::queue<int> toRemove; bool Using[100000];
void Assist(unsigned char *A, int N, int K, int R) {
for(int i=0;i<K;i++){
if(!A[i]) toRemove.push(i);
Using[i] = true;
}
for(int i=0;i<N;i++){
int req = GetRequest();
if(Using[req]){
if(!A[K + i]) toRemove.push(req);
continue;
}
int rem = toRemove.front(); toRemove.pop();
Using[rem] = false;
Using[req] = true;
if(!A[K + i]) toRemove.push(req);
PutBack(rem);
}
}
