Submission #165774

#	Time	Username	Problem	Language	Result	Execution time	Memory
165774		faremy	Last supper (IOI12_supper)	C++14	100 / 100	137 ms	9432 KiB

advisor

#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);
}

assistant

#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);
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39