#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;
int andamio[100001];
queue<int> rep[100001];
pair<int,int> st[400010];
void st_i(int j,int i=0,int pos=1){
if(i==j){
int aux=andamio[i];
if(rep[aux].size()>0) {
aux=rep[aux].front();
}
else aux=100001;
st[pos]={aux,aux};
return;
}
st[pos*2]={-1,1000000};
st[pos*2+1]=st[pos*2];
st_i((i+j)/2,i,pos*2);
st_i(j,(i+j)/2+1,pos*2+1);
st[pos].first=max(st[pos*2].first,st[pos*2+1].first);
st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}
int act;
void st_ap(int j,int i=0,int pos=1){
if(i==j){
int aux=andamio[i];
if(rep[aux].size()>0) aux=rep[aux].front();
else aux=100001;
st[pos]={aux,aux};
return;
}
if(st[pos*2].second==act) st_ap((i+j)/2,i,pos*2);
else st_ap(j,(i+j)/2+1,pos*2+1);
st[pos].first=max(st[pos*2].first,st[pos*2+1].first);
st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}
void st_ag(int j,int i=0,int pos=1){
if(i==j){
int aux=andamio[i];
if(rep[aux].size()>0) aux=rep[aux].front();
else aux=100001;
st[pos]={aux,aux};
return;
}
if(st[pos*2].first==act) st_ag((i+j)/2,i,pos*2);
else st_ag(j,(i+j)/2+1,pos*2+1);
st[pos].first=max(st[pos*2].first,st[pos*2+1].first);
st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}
int return_min(int j,int i=0,int pos=1){
if(i==j) return i;
else if(st[pos].second==st[pos*2].second) return return_min((i+j)/2,i,pos*2);
else return return_min(j,(i+j)/2+1,pos*2+1);
}
int return_max(int j,int i=0,int pos=1){
if(i==j) return i;
else if(st[pos].first==st[pos*2].first) return return_max((i+j)/2,i,pos*2);
else return return_max(j,(i+j)/2+1,pos*2+1);
}
char valor[200002];
int ult[100001];
void ComputeAdvice(int *C, int N, int K, int M) {
for(int i=0;i<N;i++){
if(i<K) {
andamio[i]=i;
valor[i]=1;
ult[i]=i;
}
rep[C[i]].push(i);
}
st_i(K-1);
for(int i=0;i<N;i++){
valor[i+K]=1;
if(st[1].second==i){
int pos=andamio[return_min(K-1)];
rep[pos].pop();
act=i;
st_ap(K-1);
ult[pos]=i+K;
}
else{
int pos=return_max(K-1);
valor[ult[andamio[pos]]]=0;
rep[C[i]].pop();
andamio[pos]=C[i];
act=st[1].first;
st_ag(K-1);
ult[C[i]]=i+K;
}
}
for(int i=0;i<N+K;i++){
WriteAdvice(valor[i]);
}
}
/*10 3 200
6 2 2 1 3 6 9 8 6 2*/
#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;
queue<int> lib;
int an[100001];
int col[100001];
void Assist(unsigned char *A, int N, int K, int R){
for(int i=0;i<N;i++){
if(i<K){
an[i]=i;
col[i]=i;
if(A[i]==0) lib.push(i);
}
else col[i]=-1;
}
for(int i=0;i<N;i++){
int c=GetRequest();
if(col[c]==-1){
int pos=0;
if(lib.size()>0){
pos=lib.front();
lib.pop();
}
PutBack(an[pos]);
col[an[pos]]=-1;
col[c]=pos;
an[pos]=c;
}
if(A[i+K]==0) lib.push(col[c]);
}
}
