#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
typedef pair<int,int> pii;
static vector<int> v[MAXN];
static bool current[MAXN];
static set<pii> nxRemove;
int getNextUsage(int i) {
if (v[i].empty()) return 1000000000;
else {
int ret = v[i].back();
return ret;
}
}
void ComputeAdvice(int *C, int N, int K, int M) {
for (int i = 0; i < N; i++)
v[C[i]].push_back(i);
for (int i = 0; i < N; i++)
reverse(v[i].begin(), v[i].end());
for (int i = 0; i < N; i++) current[i] = false;
vector<int> stk;
for (int i = 0; i < K; i++) {
stk.push_back(i);
current[i] = true;
nxRemove.insert({getNextUsage(i), i});
}
for (int i = 0; i < N; i++) {
// printf("i %d C[i] %d\n", i, C[i]);
if (current[C[i]]) {
nxRemove.erase({getNextUsage(C[i]), C[i]});
v[C[i]].pop_back();
nxRemove.insert({getNextUsage(C[i]), C[i]});
} else {
auto it = prev(nxRemove.end());
int toRemove = it->second;
nxRemove.erase(it);
v[C[i]].pop_back();
nxRemove.insert({getNextUsage(C[i]), C[i]});
// printf("toRemove %d\n", toRemove);
while (stk.back() != toRemove) {
WriteAdvice(1);
// printf("putBit %d\n", 1);
int back = stk.back();
stk.pop_back();
stk.insert(stk.begin(), back);
}
WriteAdvice(0);
// printf("putBit %d\n", 0);
stk.pop_back();
stk.insert(stk.begin(), C[i]);
current[C[i]] = true;
current[toRemove] = false;
}
}
}
#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
static bool current[MAXN];
vector<int> stk;
bool getBit(unsigned char *A) {
static int i = 0;
// printf("getBit %d\n", A[i]);
return A[i++];
}
void Assist(unsigned char *A, int N, int K, int R) {
for (int i = 0; i < K; i++) {
stk.push_back(i);
current[i] = true;
}
for (int i = 0; i < N; i++) {
int req = GetRequest();
if (current[req]) {
continue;
}
while (getBit(A)) {
int back = stk.back();
stk.pop_back();
stk.insert(stk.begin(), back);
}
PutBack(stk.back());
current[stk.back()] = false;
stk.pop_back();
stk.insert(stk.begin(), req);
current[req] = true;
}
}
