Submission #361581

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
361581	2021-01-30T16:10:55 Z	MetB	Last supper (IOI12_supper)	C++14	100 / 100	183 ms	13200 KB

advisor

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include "advisor.h"

using namespace std;

void ComputeAdvice(int *C, int N, int K, int M) {
	vector<vector<int>> last(N);
	vector<int> ans(N), ans_k(K);
	vector<int> request(N, -1);
	vector<int> ptr(N), st(N);
	set<pair<int, int>> s;

	for (int i = 0; i < N; i++) {
		last[C[i]].push_back(i);
	}

	for (int i = 0; i < N; i++) {
		last[i].push_back(N);
	}

	for (int i = 0; i < K; i++) {
		s.insert({last[i][0], i});
		st[i] = 1;
	}

	for (int i = 0; i < N; i++) {
		/*for (auto a : s) {
			cout << a.first << ' ' << a.second << endl;
		}
		cout << "----\n";*/

		request[C[i]] = i;
		if (!st[C[i]]) {
			int x = s.rbegin()->second;
			s.erase({last[x][ptr[x]], x});
			st[x] = 0;
			if (request[x] != -1) ans[request[x]] = 1;
			else ans_k[x] = 1;
			while(last[C[i]][ptr[C[i]]] <= i) ptr[C[i]]++;
			s.insert({last[C[i]][ptr[C[i]]], C[i]});
		} else {
			s.erase({last[C[i]][ptr[C[i]]], C[i]});
			while(last[C[i]][ptr[C[i]]] <= i) ptr[C[i]]++;
			s.insert({last[C[i]][ptr[C[i]]], C[i]});
		}
		st[C[i]] = 1;
	}

	for (int i = 0; i < K; i++) {
		WriteAdvice(ans_k[i]);
	}

	for (int i = 0; i < N; i++) {
		WriteAdvice(ans[i]);
	}
}

assistant

#include <iostream>
#include <vector>
#include "assistant.h"

using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
	vector<int> st(N);
	vector<int> bottom_shelf;
	for (int i = 0; i < K; i++) {
		if (A[i]) bottom_shelf.push_back(i);
		st[i] = 1;
	}

	A += K;

	for (int i = 0; i < N; i++) {
		int x = GetRequest();
		if (!st[x]) {
			st[bottom_shelf.back()] = 0;
			PutBack(bottom_shelf.back());
			bottom_shelf.pop_back();
		}
		st[x] = 1;
		if (A[i]) bottom_shelf.push_back(x);
	}

}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1028 KB	Output is correct
2	Correct	2 ms	1012 KB	Output is correct
3	Correct	3 ms	1156 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	6 ms	1380 KB	Output is correct
6	Correct	6 ms	1460 KB	Output is correct
7	Correct	6 ms	1624 KB	Output is correct
8	Correct	6 ms	1328 KB	Output is correct
9	Correct	6 ms	1244 KB	Output is correct
10	Correct	7 ms	1376 KB	Output is correct
11	Correct	7 ms	1328 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1912 KB	Output is correct
2	Correct	56 ms	6432 KB	Output is correct
3	Correct	160 ms	13200 KB	Output is correct
4	Correct	103 ms	11328 KB	Output is correct
5	Correct	123 ms	11180 KB	Output is correct
6	Correct	136 ms	11748 KB	Output is correct
7	Correct	141 ms	12376 KB	Output is correct
8	Correct	129 ms	11004 KB	Output is correct
9	Correct	90 ms	11472 KB	Output is correct
10	Correct	157 ms	12808 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	9500 KB	Output is correct
2	Correct	149 ms	11376 KB	Output is correct
3	Correct	149 ms	11704 KB	Output is correct
4	Correct	168 ms	11540 KB	Output is correct
5	Correct	140 ms	11404 KB	Output is correct
6	Correct	169 ms	12720 KB	Output is correct
7	Correct	150 ms	12668 KB	Output is correct
8	Correct	164 ms	12668 KB	Output is correct
9	Correct	136 ms	13116 KB	Output is correct
10	Correct	155 ms	12796 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1156 KB	Output is correct
2	Correct	6 ms	1160 KB	Output is correct
3	Correct	5 ms	1200 KB	Output is correct
4	Correct	6 ms	1368 KB	Output is correct
5	Correct	6 ms	1368 KB	Output is correct
6	Correct	6 ms	1364 KB	Output is correct
7	Correct	6 ms	1328 KB	Output is correct
8	Correct	7 ms	1456 KB	Output is correct
9	Correct	8 ms	1328 KB	Output is correct
10	Correct	8 ms	1688 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	11316 KB	Output is correct - 120000 bits used
2	Correct	145 ms	11500 KB	Output is correct - 122000 bits used
3	Correct	150 ms	11460 KB	Output is correct - 125000 bits used
4	Correct	152 ms	11704 KB	Output is correct - 125000 bits used
5	Correct	156 ms	11696 KB	Output is correct - 125000 bits used
6	Correct	155 ms	11452 KB	Output is correct - 125000 bits used
7	Correct	183 ms	11452 KB	Output is correct - 124828 bits used
8	Correct	159 ms	11680 KB	Output is correct - 124910 bits used
9	Correct	165 ms	11696 KB	Output is correct - 125000 bits used
10	Correct	150 ms	11612 KB	Output is correct - 125000 bits used