Submission #761864

#	Time	Username	Problem	Language	Result	Execution time	Memory
761864		SanguineChameleon	Last supper (IOI12_supper)	C++17	100 / 100	115 ms	12352 KiB

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39