#include "advisor.h"
#include <queue>
#include <map>
#include <set>
using namespace std;
static const int MAXN=100010;
static char changable[MAXN*2]; // final bit push
static set<int> S[MAXN]; // S[i] appears at elements' turn
static map<int,int> B; // now state, first is color, second is index
static priority_queue<pair<int, int> > Change; //appearance(inf none, N+1), element of B
void ComputeAdvice(int *C, int N, int K, int M)
{
for(int i=0;i<N+K;i++) changable[i]=0;
for(int i=0;i<N;i++)
S[C[i]].insert(i);
for(int i=0;i<K;i++)
{
B[i]=i;
if(!S[i].empty())
{
set<int>::iterator it=S[i].end();
--it;
Change.push(make_pair(*it,i));
}
else Change.push(make_pair(N+1,i));
}
for(int i=0;i<N;i++)
{
map<int, int>::iterator it=B.find(C[i]);
if(it!=B.end())
B[C[i]]=K+i;
else
{
S[C[i]].erase(i);
pair<int, int> tmp=Change.top();
Change.pop();
int tochange=tmp.second;
changable[B[tochange]]=1;
map<int,int>::iterator todel=B.find(tochange);
B.erase(todel);
B[C[i]]=K+i;
if(!S[C[i]].empty() )
{
set<int>::iterator it=S[C[i]].end();
--it;
Change.push(make_pair(*it,C[i]));
}
else Change.push(make_pair(N+1,C[i]));
}
}
for(int i=0;i<N+K;i++)
WriteAdvice(changable[i]);
return;
}
#include "assistant.h"
#include<set>
using namespace std;
set<int> one; //changable
set<int> zero; //not changable
void Assist(unsigned char *A, int N, int K, int R)
{
for(int i=0;i<K;i++)
{
if(A[i]) one.insert(i);
else zero.insert(i);
}
for(int i=0;i<N;i++)
{
int s=A[i+K];
int r=GetRequest();
set<int>::iterator oit=one.find(r);
set<int>::iterator zit=zero.find(r);
if(oit!=one.end())
{
if(s==0)
{
one.erase(oit);
zero.insert(r);
}
continue;
}
if(zit!=zero.end())
{
if(s==1)
{
zero.erase(zit);
one.insert(r);
}
continue;
}
set<int>::iterator it=one.begin();
PutBack(*it);
one.erase(it);
if(s==0) zero.insert(r);
else one.insert(r);
}
return;
}
