#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define ins insert
#define mp make_pair
#define f first
#define s second
const int mx = 200005;
int col[mx];
int nex[mx]; //next needed
int curpos[mx]; //current position of a color
bool getK[mx]; //does this index get kicked off before needed again
bool inScaf[mx]; //is this color in the scaffold
void ComputeAdvice(int *C, int N, int K, int M) {
//cout << N << " " << K << "\n";
// cout << "B1" << "\n";
// cout.flush();
for(int i = 0; i < N; i++){
col[i+K] = C[i];
//cout << C[i] << " ";
}
//cout << "\n";
for(int i = 0; i < K; i++){
col[i] = i;
}
for(int i = 0; i < N; i++){
curpos[i] = N+K;
}
for(int i = N-1; i >= -K; i--){
nex[i+K] = curpos[col[i+K]];
curpos[col[i+K]] = i+K;
//cout << i+K << " " << nex[i+K] << "\n";
}
// cout << "B2" << "\n";
// cout.flush();
set<pi> pq; //when needed again, index+K
for(int i = 0; i < K; i++){
pq.ins(mp(nex[i-K+K], i-K+K));
inScaf[i] = 1;
}
for(int i = 0; i < N; i++){
if(inScaf[col[i+K]]){
pi a = *(pq.begin());
assert(i+K == a.f);
pq.erase(a);
pq.ins(mp(nex[i+K], i+K));
continue;
}
pi a = *(prev(pq.end()));
//cout << i << " " << a.f << " " << a.s << "\n";
pq.erase(a);
getK[a.s] = 1; //got kicked off
pq.ins(mp(nex[i+K], i+K));
//cout << col[i+K] << " " << col[a.s] << "\n";
inScaf[col[i+K]] = 1;
inScaf[col[a.s]] = 0;
}
// cout << "B3" << "\n";
// cout.flush();
for(int i = -K; i < N; i++){
WriteAdvice(getK[i+K]);
//cout << i+K << " " << col[i+K] << " " << nex[i+K] << " " << getK[i+K] << "\n";
}
// cout << "B5" << "\n";
// cout.flush();
}
#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define ins insert
const int mx = 200005;
int col2[mx];
bool getK2[mx]; //does this index get kicked off before needed again
bool inScaf2[mx]; //is this col2or in the scaffold
set<int> unq2; //indices of C that have not been queried yet
int lastc[mx];
void Assist(unsigned char *A, int N, int K, int R) {
for(int i = 0; i < R; i++){
getK2[i] = A[i];
}
for(int i = 0; i < K; i++){
col2[i] = i;
}
for(int i = 0; i < N; i++){
if(i < K) inScaf2[i] = 1;
else inScaf2[i] = 0;
}
for(int i = 0; i < K; i++){
unq2.insert(i-K+K);
}
for(int i = 0; i < N; i++){
lastc[i] = -1;
}
for(int i = 0; i < N; i++){
//cout << "i: " << i << "\n";
col2[i+K] = GetRequest();
if(inScaf2[col2[i+K]]){
if(unq2.count(lastc[col2[i+K]])) unq2.erase(lastc[col2[i+K]]);
unq2.ins(i+K);
continue; //do nothing
}
inScaf2[col2[i+K]] = 1;
while(true){
int a = *(unq2.begin());
unq2.erase(a);
if(getK2[a]){
// cout << "a: " << a << " " << col2[a] << "\n";
// cout.flush();
PutBack(col2[a]);
inScaf2[col2[a]] = 0;
break;
}
}
unq2.insert(i+K);
lastc[col2[i+K]] = i+K;
}
}
