#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;
const int maxn = 1e5 + 10;
int last[maxn], bitcnt;
int getlog(int x)
{
for (int i = 0; i < 20; ++ i)
{
int p = (1 << i);
if(p > x)return i-1;
}
}
void givebits(int x)
{
for (int i = 0; i < bitcnt; ++ i)
{
if((1 << i) & x)WriteAdvice(1);
else WriteAdvice(0);
}
}
map < int, int > mp;
deque < int > as[maxn];
int init[maxn], p[maxn];
vector < int > rem[maxn], used[maxn];
int pt[maxn], ptrem[maxn];
void ComputeAdvice(int *C, int N, int K, int M)
{
mp.clear();
int n = N;
int k = K;
int m = M;
bitcnt = getlog(N) + 1;
for (int i = 0; i < n; ++ i)
as[C[i]].push_back(i);
for (int i = 0; i < n; ++ i)
as[i].push_back(n);
set < pair < int, int > > q;
vector < pair < int, int > > g[n+1];
for (int i = 0; i < K; ++ i)
{
mp[i] = 1;
g[i].push_back(make_pair(0, -i-1));
q.insert(make_pair(as[i].front(), i));
}
for (int i = 0; i < n; ++ i)
{
used[C[i]].push_back(i);
if(mp[C[i]])
{
as[C[i]].pop_front();
int newlast = as[C[i]].front();
q.erase(make_pair(i, C[i]));
q.insert(make_pair(newlast, C[i]));
}
else
{
pair < int, int > w = *q.rbegin();
int index = w.second;
q.erase(w);
as[C[i]].pop_front();
rem[index].push_back(i);
int newlast = as[C[i]].front();
q.insert(make_pair(newlast, C[i]));
mp[index] = 0;
mp[C[i]] = 1;
}
}
for (int i = 0;i < n; ++ i)
{
used[i].push_back(n);
rem[i].push_back(n);
}
for (int i = 0; i < k; ++ i)
{
if(used[i][0] < rem[i][0])init[i] = 1;
else init[i] = 0;
}
for (int i = 0; i < n; ++ i)
{
int value = C[i];
pt[value] ++;
while(rem[value][ptrem[value]] <= i)
{
ptrem[value] ++;
}
if(used[value][pt[value]]< rem[value][ptrem[value]])p[i] = 1;
else p[i] = 0;
}
for (int i = 0; i < k; ++ i)
{
WriteAdvice(init[i]);
// cout << init[i+1] << " ";
}
// cout << endl;
for (int i = 0; i < n; ++ i)
{
WriteAdvice(p[i]);
// cout << p[i] << " ";
}
//cout << endl;
}
#include <bits/stdc++.h>
#include "assistant.h"
#define pb push_back
using namespace std;
const int maxnn = 1e5 + 10;
vector < int > g;
int n, bitche;
int getlog2(int x)
{
for (int i = 0; i < 20; ++ i)
{
int p = (1 << i);
if(p > x)return i-1;
}
}
int curr_bit = 0;
int get_bits()
{
int ans = 0;
for (int i = 0; i < bitche; ++ i)
{
if(g[curr_bit])ans = (ans | (1 << i));
curr_bit ++;
}
return ans;
}
void Assist(unsigned char *A, int N, int K, int R)
{
// cout << R << endl;
n = N;
bitche = getlog2(N) + 1;
for (int i = 0; i < R; ++ i)
{
g.pb(A[i]);
//cout << A[i] << " ";
} //cout << endl;
set < int > passive, active;
map < int, int > mp;
int curr_bit = 0;
for (int i = 0; i < K; ++ i)
{
if(!g[0])passive.insert(i);
else active.insert(i);
mp[i] = 1;
curr_bit ++;
}
for (int i = 0; i < N; ++ i)
{
int curr = GetRequest();
int type = g[curr_bit];
curr_bit ++;
if(mp[curr])
{
passive.erase(curr);
active.erase(curr);
}
else
{
assert(passive.size());
//cout << passive.size() << " is passive.size bef del " << endl;
int del = *passive.rbegin();
passive.erase(del);
PutBack(del);
mp[del] = 0;
}
mp[curr] = 1;
if(type == 0)passive.insert(curr);
else active.insert(curr);
}
}
