Submission #761877

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
761877	2023-06-20T10:51:47 Z	SanguineChameleon	Last supper (IOI12_supper)	C++17	100 / 100	104 ms	12568 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) {
	vector<int> free;
	set<int> S;
	for (int i = 0; i < K; i++) {
		if (A[i] == 1) {
			free.push_back(i);
		}
		S.insert(i);
	}
	for (int i = 0; i < N; i++) {
		int X = GetRequest();
		if (S.find(X) == S.end()) {
			int Y = free.back();
			PutBack(Y);
			free.pop_back();
			S.erase(Y);
			S.insert(X);
		}
		if (A[K + i] == 1) {
			free.push_back(X);
		}
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2952 KB	Output is correct
2	Correct	2 ms	2952 KB	Output is correct
3	Correct	3 ms	3100 KB	Output is correct
4	Correct	3 ms	2980 KB	Output is correct
5	Correct	4 ms	3140 KB	Output is correct
6	Correct	5 ms	3232 KB	Output is correct
7	Correct	4 ms	3260 KB	Output is correct
8	Correct	6 ms	3396 KB	Output is correct
9	Correct	6 ms	3312 KB	Output is correct
10	Correct	6 ms	3408 KB	Output is correct
11	Correct	6 ms	3400 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3664 KB	Output is correct
2	Correct	38 ms	5960 KB	Output is correct
3	Correct	95 ms	12568 KB	Output is correct
4	Correct	61 ms	8376 KB	Output is correct
5	Correct	65 ms	8476 KB	Output is correct
6	Correct	79 ms	8980 KB	Output is correct
7	Correct	89 ms	10380 KB	Output is correct
8	Correct	79 ms	11000 KB	Output is correct
9	Correct	52 ms	7176 KB	Output is correct
10	Correct	99 ms	11400 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	9504 KB	Output is correct
2	Correct	96 ms	10920 KB	Output is correct
3	Correct	93 ms	11004 KB	Output is correct
4	Correct	98 ms	10792 KB	Output is correct
5	Correct	87 ms	9836 KB	Output is correct
6	Correct	94 ms	11124 KB	Output is correct
7	Correct	93 ms	10900 KB	Output is correct
8	Correct	91 ms	12116 KB	Output is correct
9	Correct	78 ms	9584 KB	Output is correct
10	Correct	98 ms	11008 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3252 KB	Output is correct
2	Correct	5 ms	3444 KB	Output is correct
3	Correct	5 ms	3156 KB	Output is correct
4	Correct	5 ms	3132 KB	Output is correct
5	Correct	5 ms	3164 KB	Output is correct
6	Correct	6 ms	3168 KB	Output is correct
7	Correct	5 ms	3260 KB	Output is correct
8	Correct	5 ms	3396 KB	Output is correct
9	Correct	5 ms	3292 KB	Output is correct
10	Correct	6 ms	3652 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	10528 KB	Output is correct - 120000 bits used
2	Correct	92 ms	10812 KB	Output is correct - 122000 bits used
3	Correct	94 ms	11080 KB	Output is correct - 125000 bits used
4	Correct	104 ms	11000 KB	Output is correct - 125000 bits used
5	Correct	95 ms	11092 KB	Output is correct - 125000 bits used
6	Correct	94 ms	11052 KB	Output is correct - 125000 bits used
7	Correct	94 ms	11008 KB	Output is correct - 124828 bits used
8	Correct	95 ms	10940 KB	Output is correct - 124910 bits used
9	Correct	92 ms	10972 KB	Output is correct - 125000 bits used
10	Correct	96 ms	12148 KB	Output is correct - 125000 bits used