Submission #65205

#	Time	Username	Problem	Language	Result	Execution time	Memory
65205		gnoor	Last supper (IOI12_supper)	C++17	100 / 100	213 ms	12000 KiB

advisor

#include "advisor.h"

#include <queue>
#include <algorithm>
#include <vector>
#include <cstdio>


using namespace std;

int last[100100];
int nxt[100100];

priority_queue<pair<int,int>> q;

int ans[200100];
int posinq[100100];
bool ins[100100];

void ComputeAdvice(int *C, int N, int K, int M) {
	for (int i=0;i<N;i++) {
		last[i]=N;
	}

	for (int i=N-1;i>=0;i--) {
		nxt[i]=last[C[i]];
		last[C[i]]=i;
	}

	for (int i=0;i<K;i++) {
		q.push({last[i],i});
		posinq[i]=i;
		ins[i]=true;
	}
	for (int i=0;i<N;i++) {
		if (ins[C[i]]) {
			//is in s
			ans[posinq[C[i]]]=1;
			posinq[C[i]]=i+K;
			q.push({nxt[i],C[i]});
		} else {
			while (!q.empty()&&!ins[q.top().second]) q.pop();
			ans[posinq[q.top().second]]=0;
			ins[q.top().second]=false;
			q.pop();

			posinq[C[i]]=i+K;
			ins[C[i]]=true;
			q.push({nxt[i],C[i]});
		}
	}
	for (int i=0;i<N+K;i++) WriteAdvice(ans[i]);
}

assistant

#include "assistant.h"

#include <vector>
#include <set>
#include <cstdio>

using namespace std;

int cnt[100100];
bool removable[100100];

set<int> rminscf;
set<int> inscf;

void Assist(unsigned char *A, int N, int K, int R) {

	for (int i=0;i<K;i++) {
		if (A[i]) inscf.insert(i);
		else rminscf.insert(i);
	}

	int req;
	for (int i=0;i<N;i++) {
		req=GetRequest();
		if (inscf.find(req)==inscf.end()&&rminscf.find(req)==rminscf.end()) {
			//req is not in scf
			PutBack(*rminscf.begin());
			rminscf.erase(rminscf.begin());
		} else {
			inscf.erase(req);
			rminscf.erase(req);
		}
		
		if (A[i+K]) inscf.insert(req);
		else rminscf.insert(req);
	}

}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39