oj.uz

Submission #761620

# Submission time Handle Problem Language Result Execution time Memory
761620 2023-06-20T05:43:25 Z SanguineChameleon Last supper (IOI12_supper) C++17
43 / 100
 293 ms 23248 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

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

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

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

const int maxK = 1e5 + 20;
int colors[maxK];

void Assist(unsigned char *A, int N, int K, int R) {
	int L = 1;
	while ((1 << L) < K) {
		L++;
	}
	set<int> S;
	for (int i = 0; i < K; i++) {
		colors[i] = i;
		S.insert(i);
	}
	int pt = 0;
	for (int i = 0; i < N; i++) {
		int C = GetRequest();
		if (S.find(C) != S.end()) {
			continue;
		}
		int pos = 0;
		for (int j = 0; j < L; j++) {
			pos |= (A[pt + j] << j);
		}
		pt += L;
		PutBack(colors[pos]);
		S.erase(colors[pos]);
		S.insert(C);
		colors[pos] = C;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2948 KB Output is correct
2 Correct 1 ms 2948 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 4 ms 2972 KB Output is correct
5 Correct 5 ms 3284 KB Output is correct
6 Correct 11 ms 3564 KB Output is correct
7 Correct 7 ms 3280 KB Output is correct
8 Correct 11 ms 3720 KB Output is correct
9 Correct 11 ms 3596 KB Output is correct
10 Correct 9 ms 3632 KB Output is correct
11 Correct 9 ms 3572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4120 KB Output is correct
2 Correct 85 ms 7824 KB Output is correct
3 Correct 270 ms 21916 KB Output is correct
4 Correct 164 ms 14604 KB Output is correct
5 Correct 210 ms 16492 KB Output is correct
6 Correct 242 ms 17168 KB Output is correct
7 Correct 228 ms 17976 KB Output is correct
8 Correct 224 ms 20076 KB Output is correct
9 Correct 109 ms 9240 KB Output is correct
10 Correct 223 ms 18300 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 14336 KB Output is correct
2 Correct 221 ms 16816 KB Output is correct
3 Correct 229 ms 16976 KB Output is correct
4 Correct 228 ms 16244 KB Output is correct
5 Correct 181 ms 13180 KB Output is correct
6 Correct 238 ms 18172 KB Output is correct
7 Correct 225 ms 17776 KB Output is correct
8 Correct 278 ms 23248 KB Output is correct
9 Correct 159 ms 13792 KB Output is correct
10 Correct 255 ms 18244 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3204 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 16800 KB Output is partially correct - 772365 bits used
2 Correct 253 ms 16728 KB Output is partially correct - 742095 bits used
3 Correct 223 ms 17012 KB Output is partially correct - 712470 bits used
4 Correct 221 ms 16952 KB Output is partially correct - 712005 bits used
5 Correct 223 ms 16988 KB Output is partially correct - 710610 bits used
6 Correct 226 ms 17196 KB Output is partially correct - 712155 bits used
7 Correct 228 ms 16920 KB Output is partially correct - 711090 bits used
8 Correct 238 ms 17068 KB Output is partially correct - 713340 bits used
9 Correct 223 ms 16992 KB Output is partially correct - 712830 bits used
10 Correct 293 ms 21836 KB Output is partially correct - 1117620 bits used