Submission #761864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
761864	2023-06-20T10:37:44 Z	SanguineChameleon	Last supper (IOI12_supper)	C++17	100 / 100	115 ms	12352 KB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
vector<int> pos[maxN];
int A[maxN * 2];

void ComputeAdvice(int *C, int N, int K, int M) {
	for (int i = N - 1; i >= 0; i--) {
		pos[C[i]].push_back(i);
	}
	set<pair<int, int>> S;
	for (int i = 0; i < K; i++) {
		S.emplace(pos[i].empty() ? N : pos[i].back(), i);
	}
	for (int i = 0; i < N; i++) {
		if (S.begin()->first == i) {
			S.erase(S.begin());
		}
		else {
			A[prev(S.end())->second] = 1;
			S.erase(prev(S.end()));
		}
		pos[C[i]].pop_back();
		S.emplace(pos[C[i]].empty() ? N : pos[C[i]].back(), K + i);
	}
	for (int i = 0; i < K + N; i++) {
		WriteAdvice(A[i]);
	}
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
	set<int> free;
	set<int> S;
	for (int i = 0; i < K; i++) {
		if (A[i] == 1) {
			free.insert(i);
		}
		S.insert(i);
	}
	for (int i = 0; i < N; i++) {
		int X = GetRequest();
		if (S.find(X) == S.end()) {
			int Y = *free.begin();
			PutBack(Y);
			free.erase(Y);
			S.erase(Y);
			S.insert(X);
		}
		if (A[K + i] == 0) {
			free.erase(X);
		}
		else {
			free.insert(X);
		}
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2956 KB	Output is correct
2	Correct	1 ms	2956 KB	Output is correct
3	Correct	3 ms	3088 KB	Output is correct
4	Correct	3 ms	2964 KB	Output is correct
5	Correct	5 ms	3112 KB	Output is correct
6	Correct	5 ms	3108 KB	Output is correct
7	Correct	5 ms	3244 KB	Output is correct
8	Correct	5 ms	3372 KB	Output is correct
9	Correct	6 ms	3240 KB	Output is correct
10	Correct	5 ms	3376 KB	Output is correct
11	Correct	7 ms	3376 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	3680 KB	Output is correct
2	Correct	40 ms	5568 KB	Output is correct
3	Correct	106 ms	12352 KB	Output is correct
4	Correct	62 ms	8056 KB	Output is correct
5	Correct	84 ms	7876 KB	Output is correct
6	Correct	81 ms	8736 KB	Output is correct
7	Correct	93 ms	10212 KB	Output is correct
8	Correct	80 ms	10540 KB	Output is correct
9	Correct	55 ms	6704 KB	Output is correct
10	Correct	100 ms	11136 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	9228 KB	Output is correct
2	Correct	107 ms	10748 KB	Output is correct
3	Correct	100 ms	10828 KB	Output is correct
4	Correct	102 ms	10584 KB	Output is correct
5	Correct	94 ms	9812 KB	Output is correct
6	Correct	115 ms	10816 KB	Output is correct
7	Correct	115 ms	10688 KB	Output is correct
8	Correct	90 ms	11676 KB	Output is correct
9	Correct	84 ms	9932 KB	Output is correct
10	Correct	98 ms	10796 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3220 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	5 ms	3120 KB	Output is correct
4	Correct	4 ms	3108 KB	Output is correct
5	Correct	5 ms	3108 KB	Output is correct
6	Correct	5 ms	3236 KB	Output is correct
7	Correct	5 ms	3236 KB	Output is correct
8	Correct	5 ms	3236 KB	Output is correct
9	Correct	5 ms	3236 KB	Output is correct
10	Correct	6 ms	3640 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	10344 KB	Output is correct - 120000 bits used
2	Correct	95 ms	10616 KB	Output is correct - 122000 bits used
3	Correct	98 ms	10932 KB	Output is correct - 125000 bits used
4	Correct	98 ms	10848 KB	Output is correct - 125000 bits used
5	Correct	113 ms	10872 KB	Output is correct - 125000 bits used
6	Correct	114 ms	10928 KB	Output is correct - 125000 bits used
7	Correct	108 ms	10804 KB	Output is correct - 124828 bits used
8	Correct	104 ms	10808 KB	Output is correct - 124910 bits used
9	Correct	105 ms	10848 KB	Output is correct - 125000 bits used
10	Correct	95 ms	11628 KB	Output is correct - 125000 bits used