Submission #114332

#	Time	Username	Problem	Language	Result	Execution time	Memory
114332		nxteru	Last supper (IOI12_supper)	C++14	100 / 100	140 ms	8312 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n,k,nex[200005],p[200005],ex[200005],ans[200005];
void ComputeAdvice(int *C, int N, int K, int M) {
	n=N,k=K;
	for(int i=0;i<n;i++)p[i]=n,ex[i]=-1;
	for(int i=n-1;i>=0;i--){
		nex[i]=p[C[i]];
		p[C[i]]=i;
	}
	priority_queue<P>d;
	for(int i=0;i<k;i++)d.push(P(p[i],i)),ex[i]=i;
	for(int i=0;i<n;i++){
		int c=C[i];
		if(ex[c]!=-1)ans[ex[c]]=1;
		else{
			int y;
			while(1){
				y=d.top().second;
				d.pop();
				if(ex[y]==-1)continue;
				ex[y]=-1;
				break;
			}
		}
		ex[c]=k+i;
		d.push(P(nex[i],c));
	}
	for(int i=0;i<k+n;i++)WriteAdvice(ans[i]);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
set<int>x,y;
void Assist(unsigned char *A, int N, int K, int R) {
	for(int i=0;i<K;i++){
		if(A[i]==0)x.insert(i);
		else y.insert(i);
	}
	for(int i=K;i<N+K;i++){
		int c=GetRequest();
		if(y.find(c)!=y.end())y.erase(c);
		else{
			PutBack(*x.begin());
			x.erase(x.begin());
		}
		if(A[i]==0)x.insert(c);
		else y.insert(c);
	}
}

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