oj.uz

답안 #361581

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361581 2021-01-30T16:10:55 Z MetB 최후의 만찬 (IOI12_supper) C++14
100 / 100
 183 ms 13200 KB 
#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]);
	}
}

#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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