oj.uz

Submission #165774

# Submission time Handle Problem Language Result Execution time Memory
165774 2019-11-28T16:32:45 Z faremy Last supper (IOI12_supper) C++14
100 / 100
 137 ms 9432 KB 
#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);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 784 KB Output is correct
2 Correct 4 ms 660 KB Output is correct
3 Correct 5 ms 816 KB Output is correct
4 Correct 5 ms 1068 KB Output is correct
5 Correct 7 ms 1164 KB Output is correct
6 Correct 7 ms 1324 KB Output is correct
7 Correct 7 ms 1224 KB Output is correct
8 Correct 7 ms 1120 KB Output is correct
9 Correct 7 ms 1092 KB Output is correct
10 Correct 8 ms 1272 KB Output is correct
11 Correct 8 ms 1116 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1776 KB Output is correct
2 Correct 41 ms 4584 KB Output is correct
3 Correct 83 ms 9432 KB Output is correct
4 Correct 72 ms 6112 KB Output is correct
5 Correct 74 ms 6376 KB Output is correct
6 Correct 78 ms 7392 KB Output is correct
7 Correct 81 ms 8440 KB Output is correct
8 Correct 68 ms 6880 KB Output is correct
9 Correct 68 ms 6064 KB Output is correct
10 Correct 83 ms 8672 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6880 KB Output is correct
2 Correct 88 ms 8416 KB Output is correct
3 Correct 83 ms 8672 KB Output is correct
4 Correct 82 ms 8672 KB Output is correct
5 Correct 78 ms 8416 KB Output is correct
6 Correct 81 ms 8392 KB Output is correct
7 Correct 81 ms 8728 KB Output is correct
8 Correct 80 ms 7904 KB Output is correct
9 Correct 78 ms 8416 KB Output is correct
10 Correct 82 ms 8416 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1076 KB Output is correct
2 Correct 7 ms 1208 KB Output is correct
3 Correct 7 ms 1092 KB Output is correct
4 Correct 7 ms 1092 KB Output is correct
5 Correct 7 ms 1008 KB Output is correct
6 Correct 7 ms 1008 KB Output is correct
7 Correct 8 ms 1008 KB Output is correct
8 Correct 7 ms 1096 KB Output is correct
9 Correct 8 ms 1192 KB Output is correct
10 Correct 8 ms 1264 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8704 KB Output is correct - 120000 bits used
2 Correct 81 ms 8352 KB Output is correct - 122000 bits used
3 Correct 87 ms 8416 KB Output is correct - 125000 bits used
4 Correct 92 ms 8496 KB Output is correct - 125000 bits used
5 Correct 82 ms 8672 KB Output is correct - 125000 bits used
6 Correct 137 ms 8672 KB Output is correct - 125000 bits used
7 Correct 81 ms 8672 KB Output is correct - 124828 bits used
8 Correct 82 ms 8416 KB Output is correct - 124910 bits used
9 Correct 81 ms 8672 KB Output is correct - 125000 bits used
10 Correct 79 ms 7592 KB Output is correct - 125000 bits used