#include "advisor.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
int seen[nmax];
int nxt_seen[nmax];
set< pair<int/*seen next*/,int/*id*/> > s;
int when_pushed[nmax];
set<int> cut_moment[nmax];
vector<int> there[nmax];
int check_next_moment(int pos,int after)
{
if(there[pos].size()==0)return 0;
int p=upper_bound(there[pos].begin(),there[pos].end(),after)-there[pos].begin();
p=there[pos][p];
set<int>::iterator it=cut_moment[pos].upper_bound(after);
int q=*it;
//cout<<pos<<" "<<after<<" "<<p<<" "<<q<<endl;
return p<q;
}
void ComputeAdvice(int *C,int N,int K,int M)
{
for(int i=0;i<N;i++)
seen[i]=N;
for(int i=N-1;i>=0;i--)
{
nxt_seen[i]=seen[C[i]];
seen[C[i]]=i;
}
for(int i=0;i<K;i++)
s.insert({nxt_seen[i],i});
for(int i=0;i<N;i++)
if(s.count({i,C[i]}))
{
s.erase({i,C[i]});
s.insert({nxt_seen[i],C[i]});
}
else
{
//cut the furthest
set< pair<int/*seen next*/,int/*id*/> >::iterator it=s.end();
it--;
int which=(*it).second;
cut_moment[which].insert(i);
//cout<<"pushed cut moment "<<which<<" "<<i<<endl;
when_pushed[C[i]]=i;
s.erase(it);
s.insert({nxt_seen[i],C[i]});
}
for(int i=0;i<N;i++)
there[C[i]].push_back(i);
for(int i=0;i<N;i++)
{
cut_moment[i].insert(N);
there[i].push_back(N);
}
for(int i=0;i<K;i++)
WriteAdvice(check_next_moment(i,-1));
for(int i=0;i<N;i++)
WriteAdvice(check_next_moment(C[i],i));
}
#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
set<int> active,passive;
void Assist(unsigned char *A, int N, int K, int R)
{
for(int i=0;i<K;i++)
if(A[i]==1)active.insert(i);
else passive.insert(i);
for(int i=K;i<N+K;i++)
{
int cur=GetRequest();
if(active.count(cur))
{
active.erase(cur);
}
else
{
assert(passive.size());
int tp=*passive.begin();
passive.erase(tp);
PutBack(tp);
}
if(A[i]==1)active.insert(cur);
else passive.insert(cur);
}
}
