#include "advisor.h"
#include <vector>
#include <queue>
struct Paint
{
Paint(int c, int n) : color(c), next(n) {}
int color, next;
bool operator <(const Paint &other) const
{
return (next < other.next);
}
};
void ComputeAdvice(int *C, int N, int K, int M)
{
std::vector<int> needed;
for (int iColor = 0; iColor < K; iColor++)
needed.emplace_back(iColor);
for (int iWant = 0; iWant < N; iWant++)
needed.emplace_back(C[iWant]);
std::vector<int> nextUse(N + K, N + K);
std::vector<int> lastSeen(N, N + K);
for (int iNeed = N + K - 1; iNeed > -1; iNeed--)
{
nextUse[iNeed] = lastSeen[needed[iNeed]];
lastSeen[needed[iNeed]] = iNeed;
}
std::vector<bool> keep(N + K, false);
std::vector<int> lastNeeded(N, 0);
std::priority_queue<Paint> scaffold;
std::vector<bool> inScaffold(N, false);
int scaffoldCnt = 0;
for (int iNeed = 0; iNeed < N + K; iNeed++)
{
if (!inScaffold[needed[iNeed]])
{
if (scaffoldCnt < K)
scaffoldCnt++;
else
{
inScaffold[scaffold.top().color] = false;
scaffold.pop();
}
inScaffold[needed[iNeed]] = true;
scaffold.emplace(needed[iNeed], nextUse[iNeed]);
lastNeeded[needed[iNeed]] = iNeed;
}
else
{
keep[lastNeeded[needed[iNeed]]] = true;
scaffold.emplace(needed[iNeed], nextUse[iNeed]);
lastNeeded[needed[iNeed]] = iNeed;
}
}
for (bool adviceBit : keep)
WriteAdvice(adviceBit);
}
#include "assistant.h"
#include <vector>
void Assist(unsigned char *A, int N, int K, int R)
{
std::vector<int> uselessColors;
std::vector<bool> inScaffold(N, false);
int iNeed = 0;
for (; iNeed < K; iNeed++)
{
inScaffold[iNeed] = true;
if (A[iNeed] == 0)
uselessColors.emplace_back(iNeed);
}
for (; iNeed < N + K; iNeed++)
{
int needed = GetRequest();
if (!inScaffold[needed])
{
PutBack(uselessColors.back());
inScaffold[uselessColors.back()] = false;
uselessColors.pop_back();
inScaffold[needed] = true;
}
if (A[iNeed] == 0)
uselessColors.emplace_back(needed);
}
}
