#include<bits/stdc++.h>
#include "advisor.h"
#define fi first
#define se second
using namespace std;
const int NN=1e5;
int tmpnxt[NN+10];
int nxt[NN+10];
int en[NN+10];
bool useful[NN+10];
vector<int> can_rm[NN+10];
set<pair<int,int>> pq;
set<int> st;
set<int> okrm2;
set<int> nokrm2;
void ComputeAdvice(int *C,int N,int K,int M)
{
for(int i=0;i<N;i++)
tmpnxt[i]=N;
for(int i=N-1;i>=0;i--)
{
nxt[i]=tmpnxt[C[i]];
tmpnxt[C[i]]=i;
}
for(int i=0;i<K;i++)
pq.insert({tmpnxt[i],i});
for(int i=0;i<N;i++)
{
if(pq.find({i,C[i]})!=pq.end())
en[i]=-1;
else
{
en[i]=(prev(pq.end())->se);
pq.erase(prev(pq.end()));
pq.insert({i,C[i]});
}
tmpnxt[C[i]]=nxt[i];
pq.erase({i,C[i]});
pq.insert({nxt[i],C[i]});
}
for(auto v:pq)
st.insert(v.se);
for(int i=N-1;i>=0;i--)
{
if(en[i]==-1)
{
if(!useful[C[i]])
{
can_rm[C[i]].push_back(i);
useful[C[i]]=true;
}
}
else
{
if(!useful[C[i]])
can_rm[C[i]].push_back(i);
st.erase(C[i]);
st.insert(en[i]);
useful[en[i]]=false;
}
}
for(int i=0;i<K;i++)
{
if(!useful[i])
can_rm[i].push_back(-1);
okrm2.insert(i);
}
for(int i=0;i<N;i++)
{
if(nokrm2.find(C[i])!=nokrm2.end())
{
nokrm2.erase(C[i]);
okrm2.insert(C[i]);
continue;
}
else if(okrm2.find(C[i])!=okrm2.end())
continue;
while(true)
{
int v=(*okrm2.begin());
okrm2.erase(v);
if(can_rm[v].back()<i)
{
WriteAdvice(1);
can_rm[v].pop_back();
break;
}
WriteAdvice(0);
nokrm2.insert(v);
}
okrm2.insert(C[i]);
}
return;
}
#include<bits/stdc++.h>
#include "assistant.h"
#define fi first
#define se second
using namespace std;
const int NN=1e5;
set<int> okrm;
set<int> nokrm;
void Assist(unsigned char *A,int N,int K,int R)
{
//for(int i=0;i<R;i++)
// cerr<<(int)A[i]<<" ";
//cerr<<"\n";
int it=0;
for(int i=0;i<K;i++)
okrm.insert(i);
for(int qi=1;qi<=N;qi++)
{
int x=GetRequest();
if(nokrm.find(x)!=nokrm.end())
{
nokrm.erase(x);
okrm.insert(x);
continue;
}
else if(okrm.find(x)!=okrm.end())
continue;
// must put back
for(;A[it]==0;it++)
{
nokrm.insert(*okrm.begin());
okrm.erase(okrm.begin());
}
it++;
PutBack(*okrm.begin());
okrm.erase(okrm.begin());
okrm.insert(x);
}
return;
}
