#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
typedef pair<int,int> pii;
static vector<int> v[MAXN];
static int bitNum = 1;
static int current[MAXN];
static set<pii> nxRemove;
void putNum(int x) {
// printf("putNum %d\n", x);
for (int i = 0; i < bitNum; i++)
WriteAdvice(!!((x >> i) & 1));
}
int getNextUsage(int i) {
if (v[i].empty()) return 1000000000;
else {
int ret = v[i].back();
return ret;
}
}
void ComputeAdvice(int *C, int N, int K, int M) {
while ((1 << bitNum) < K) bitNum++;
for (int i = 0; i < N; i++)
v[C[i]].push_back(i);
for (int i = 0; i < N; i++)
reverse(v[i].begin(), v[i].end());
for (int i = 0; i < N; i++) current[i] = -1;
for (int i = 0; i < K; i++) {
current[i] = i;
nxRemove.insert({getNextUsage(i), i});
}
for (int i = 0; i < N; i++) {
// printf("request %d\n", C[i]);
// for (int k = 0; k < N; k++)
// printf("current[%d] %d\n", k, current[k]);
// printf("nxRemove: ");
// for (pii p : nxRemove) printf(" (%d,%d)", p.first, p.second);
// printf("\n");
if (current[C[i]] != -1) {
nxRemove.erase({getNextUsage(C[i]), C[i]});
v[C[i]].pop_back();
nxRemove.insert({getNextUsage(C[i]), C[i]});
} else {
auto it = prev(nxRemove.end());
int toRemove = it->second;
nxRemove.erase(it);
v[C[i]].pop_back();
nxRemove.insert({getNextUsage(C[i]), C[i]});
putNum(current[toRemove]);
current[C[i]] = current[toRemove];
current[toRemove] = -1;
}
}
}
#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
static int palette[MAXN];
static bool current[MAXN];
static int bitNum = 1;
int getNum(unsigned char *A) {
static int i = 0;
int ret = 0;
for (int k = 0; k < bitNum; k++) {
if (A[i++]) ret ^= (1 << k);
}
// printf("getNum %d\n", ret);
return ret;
}
void Assist(unsigned char *A, int N, int K, int R) {
while ((1 << bitNum) < K) bitNum++;
for (int i = 0; i < K; i++) palette[i] = i, current[i] = true;
for (int i = 0; i < N; i++) {
int req = GetRequest();
if (current[req]) {
continue;
}
int pos = getNum(A);
PutBack(palette[pos]);
current[palette[pos]] = false;
current[req] = true;
palette[pos] = req;
}
}
