#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];
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)
{
g[C[i]].push_back(make_pair(1, i));
if(mp[C[i]])
{
g[C[i]].push_back(make_pair(0, 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);
g[C[i]].push_back(make_pair(0, i));
g[index].push_back(make_pair(2, i));
as[C[i]].pop_front();
int newlast = as[C[i]].front();
q.insert(make_pair(newlast, C[i]));
mp[index] = 0;
mp[C[i]] = 1;
}
}
for (int id = 0; id < n; ++ id)
{
//cout << "solve for " << id << endl;
int last_added = 0, used = 0;
for (auto &[type, i]: g[id])
{
// cout << type << " " << i << endl;
if(type == 0)
{
last_added = i;
used = 0;
}
else if(type == 1)used = 1;
else
{
if(used == 1)
{
if(last_added > 0)p[last_added] = 1;
else init[-last_added + 1] = 1;
}
used = 0;
}
}
if(used)
{
//cout << 1 << endl;
if(last_added > 0)p[last_added] = 1;
else
{
// cout << last_added << " -> " << -last_added + 1 << endl;
init[-last_added + 1] = 1;
}
}
}
for (int i = 0; i < k; ++ i)
{
WriteAdvice(init[i+1]);
// 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
{
//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);
}
}
