#include "advisor.h"
#include <vector>
#define MAXN 100009
int heap[MAXN], poz[MAXN], d[MAXN];
inline void mySwap(int p, int q) {
int aux = heap[p];
heap[p] = heap[q];
heap[q] = aux;
poz[heap[p]] = p;
poz[heap[q]] = q;
}
inline void urcare(int p) {
while (p > 1 && d[heap[p]] > d[heap[p / 2]]) {
mySwap(p, p / 2);
p /= 2;
}
}
inline void coborare(int p) {
int q;
bool f = 1;
while (f && (q = 2 * p) <= heap[0]) {
if (q < heap[0] && d[heap[q + 1]] > d[heap[q]])
q++;
if (d[heap[q]] > d[heap[p]]) {
mySwap(p, q);
p = q;
} else
f = 0;
}
}
void ComputeAdvice(int *C, int N, int K, int M) {
std::vector < int > urm(N), last(N, N);
for (int i = N - 1; i >= 0; i--) {
urm[i] = last[C[i]];
last[C[i]] = i;
}
for (int i = 0; i < K; i++)
d[i] = last[i];
for (int i = 0; i < K; i++)
heap[++heap[0]] = i, poz[i] = i + 1;
for (int i = heap[0]; i > 0; i--)
coborare(i);
std::vector < bool > ans(N + K, 1);
std::vector < int > moment(N, -1);
for (int i = 0; i < K; i++)
moment[i] = i;
for (int i = 0; i < N; i++) {
if (poz[C[i]]) {
d[C[i]] = urm[i];
urcare(poz[C[i]]);
} else {
ans[moment[heap[1]]] = 0;
poz[heap[1]] = 0;
heap[1] = C[i];
poz[C[i]] = 1;
d[heap[1]] = urm[i];
coborare(1);
}
moment[C[i]] = i + K;
}
for (int i = 0; i < N + K; i++)
WriteAdvice(ans[i]);
}
#include "assistant.h"
#include <vector>
#include <set>
std::set < int > s;
void Assist(unsigned char *A, int N, int K, int R) {
std::vector < int > v(K), t(N, 0);
for (int i = 0; i < K; i++)
v[i] = i, t[i] = A[i];
for (int i = 0; i < K; i++)
if (t[i] == 0)
s.insert(i);
std::vector < int > avem(N, 0);
for (int i = 0; i < K; i++)
avem[i] = 1;
for (int i = 0; i < N; i++) {
int x = GetRequest();
if (!avem[x]) {
int y = *(s.begin());
PutBack(y);
s.erase(s.begin());
avem[y] = 0;
avem[x] = 1;
t[x] = A[i + K];
if (t[x] == 0)
s.insert(x);
} else {
if (t[x] == 1 && A[i + K] == 0)
s.insert(x);
else if (t[x] == 0 && A[i + K] == 1)
s.erase(s.lower_bound(x));
t[x] = A[i + K];
}
}
}
