Submission #14744

#	Time	Username	Problem	Language	Result	Execution time	Memory
14744		progressive	Last supper (IOI12_supper)	C++98	0 / 100	278 ms	25976 KiB

advisor

#include "advisor.h"
#include <queue>
#include <map>
#include <set>
using namespace std;

static const int MAXN=100010;
static char changable[MAXN*2]; // final bit push
static set<int> S[MAXN]; // S[i] appears at elements' turn
static map<int,int> B; // now state, first is color, second is index
static priority_queue<pair<int, int> > Change; //appearance(inf none, N+1), element of B
void ComputeAdvice(int *C, int N, int K, int M)
{
	for(int i=0;i<N+K;i++) changable[i]=0;
	for(int i=0;i<N;i++)
		S[C[i]].insert(i);
	for(int i=0;i<K;i++)
	{
		B[i]=i;
		if(!S[i].empty())
		{
			set<int>::iterator it=S[i].end();
			--it;
			Change.push(make_pair(*it,i));
		}
		else Change.push(make_pair(N+1,i));
	}
	for(int i=0;i<N;i++)
	{
		map<int, int>::iterator it=B.find(C[i]);
		if(it!=B.end())
			B[C[i]]=K+i;
		else
		{
			S[C[i]].erase(i);
			pair<int, int> tmp=Change.top();
			Change.pop();
			int tochange=tmp.second;
			changable[B[tochange]]=1;
			map<int,int>::iterator todel=B.find(tochange);
			B.erase(todel);
			B[C[i]]=K+i;
			if(!S[C[i]].empty() )
			{
				set<int>::iterator it=S[C[i]].end();
				--it;
				Change.push(make_pair(*it,C[i]));
			}
			else Change.push(make_pair(N+1,C[i]));
		}
	}
	for(int i=0;i<N+K;i++)
		WriteAdvice(changable[i]);
	return;
}

assistant

#include "assistant.h"
#include<set>
using namespace std;
set<int> one; //changable
set<int> zero; //not changable
void Assist(unsigned char *A, int N, int K, int R)
{
	for(int i=0;i<K;i++)
	{
		if(A[i]) one.insert(i);
		else zero.insert(i);
	}
	for(int i=0;i<N;i++)
	{
		int s=A[i+K];
		int r=GetRequest();
		set<int>::iterator oit=one.find(r);
		set<int>::iterator zit=zero.find(r);
		if(oit!=one.end())
		{
			if(s==0)
			{
				one.erase(oit);
				zero.insert(r);
			}
			continue;
		}
		if(zit!=zero.end())
		{
			if(s==1)
			{
				zero.erase(zit);
				one.insert(r);
			}
			continue;
		}
		set<int>::iterator it=one.begin();
		PutBack(*it);
		one.erase(it);
		if(s==0) zero.insert(r);
		else one.insert(r);
	}
	return;
}

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