oj.uz

Submission #14744

# Submission time Handle Problem Language Result Execution time Memory
14744 2015-06-17T15:15:16 Z progressive Last supper (IOI12_supper) C++
0 / 100
 278 ms 25976 KB 
#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;
}
#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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9968 KB Output is correct
2 Incorrect 7 ms 10056 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 11600 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 22112 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 22112 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 24888 KB Output isn't correct - not an optimal way
2 Incorrect 273 ms 25464 KB Output isn't correct - not an optimal way
3 Incorrect 278 ms 25680 KB Output isn't correct - not an optimal way
4 Incorrect 237 ms 25976 KB Output isn't correct - not an optimal way
5 Incorrect 245 ms 25976 KB Output isn't correct - not an optimal way
6 Incorrect 239 ms 25976 KB Output isn't correct - not an optimal way
7 Incorrect 251 ms 25976 KB Output isn't correct - not an optimal way
8 Incorrect 242 ms 25976 KB Output isn't correct - not an optimal way
9 Incorrect 271 ms 25976 KB Output isn't correct - not an optimal way
10 Incorrect 205 ms 25976 KB Output isn't correct - not an optimal way