제출 #349828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349828		juggernaut	Last supper (IOI12_supper)	C++14	100 / 100	153 ms	73844 KiB

advisor

//Powered by official solution
#include<bits/stdc++.h>
#include"advisor.h"
using namespace std;
int const MAXN=100000;
struct Color{
	int id;
	int np;
	Color(){}
	Color(int _id,int _np){
		id=_id;
		np=_np;
	}
};
bool operator<(Color const &a,Color const &b){
	return(a.np<b.np);
}
int nxt[MAXN];
int position[MAXN];
bool in_scaffold[MAXN];
priority_queue<Color>coda;
int solution[MAXN];
queue<int>events[MAXN];
int accumulated=0;
int counter=0;
void ComputeAdvice(int *d,int n,int k,int m){
	for(int i=0;i<n;i++)position[i]=n;
	for(int i=n-1;i>=0;i--)nxt[i]=position[d[i]],position[d[i]]=i;
	for(int j=0;j<k;j++){
		in_scaffold[j]=1;
		coda.push(Color(j,position[j]));
	}
	for(int i=0;i<n;i++){
		int color=d[i];
		if(in_scaffold[color]){
			coda.push(Color(color,nxt[i]));
			solution[i]=-1;
			events[color].push(1);
			continue;
		}		
		Color useless=coda.top();
		coda.pop();
		in_scaffold[useless.id]=0;
		coda.push(Color(color,nxt[i]));
		in_scaffold[color]=1;
		solution[i]=useless.id;
		events[useless.id].push(0);
		events[color].push(1);
	}
	for(int j=0;j<k;j++){
		if(events[j].empty()){
			WriteAdvice(0);
			continue;
		}
		if(events[j].front()==0){
			events[j].pop();
			WriteAdvice(0);
		}else WriteAdvice(1);
	}
	for(int i=0;i<n;i++){	
		int color=d[i];
		assert(events[color].front()==1);
		events[color].pop();
		if(events[color].empty()){
			WriteAdvice(0);
			continue;
		}
		if(events[color].front()==0){
			events[color].pop();
		    WriteAdvice(0);
		}else WriteAdvice(1);
	}
}

assistant

//Powered by official solution
#include<bits/stdc++.h>
#include"assistant.h"
using namespace std;
int const MAXN=100000;
bool in_the_scaffold[MAXN];
queue<int>passive;
void Assist(unsigned char *real_advice,int n,int k,int l){
	for(int i=0;i<k;i++){
		in_the_scaffold[i]=1;
		if(real_advice[i]==0)passive.push(i);
	}
	for(int i=0;i<n;i++){
		int color=GetRequest();
		if (!in_the_scaffold[color]){
			in_the_scaffold[passive.front()]=0;
			in_the_scaffold[color]=1;
			PutBack(passive.front());
			passive.pop();	
		}
		if(real_advice[k+i]==0)passive.push(color);
	}	
}

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