Submission #401815

#	Time	Username	Problem	Language	Result	Execution time	Memory
401815		Jasiekstrz	Last supper (IOI12_supper)	C++17	100 / 100	273 ms	17260 KiB

advisor

#include<bits/stdc++.h>
#include "advisor.h"
#define fi first
#define se second
using namespace std;
const int NN=1e5;
int tmpnxt[NN+10];
int nxt[NN+10];
int en[NN+10];
bool useful[NN+10];
vector<int> can_rm[NN+10];
set<pair<int,int>> pq;
set<int> st;
set<int> okrm2;
set<int> nokrm2;
void ComputeAdvice(int *C,int N,int K,int M)
{
	for(int i=0;i<N;i++)
		tmpnxt[i]=N;
	for(int i=N-1;i>=0;i--)
	{
		nxt[i]=tmpnxt[C[i]];
		tmpnxt[C[i]]=i;
	}
	for(int i=0;i<K;i++)
		pq.insert({tmpnxt[i],i});
	for(int i=0;i<N;i++)
	{
		if(pq.find({i,C[i]})!=pq.end())
			en[i]=-1;
		else
		{
			en[i]=(prev(pq.end())->se);
			pq.erase(prev(pq.end()));
			pq.insert({i,C[i]});
		}
		tmpnxt[C[i]]=nxt[i];
		pq.erase({i,C[i]});
		pq.insert({nxt[i],C[i]});
	}
	for(auto v:pq)
		st.insert(v.se);
	for(int i=N-1;i>=0;i--)
	{
		if(en[i]==-1)
		{
			if(!useful[C[i]])
			{
				can_rm[C[i]].push_back(i);
				useful[C[i]]=true;
			}
		}
		else
		{
			if(!useful[C[i]])
				can_rm[C[i]].push_back(i);
			st.erase(C[i]);
			st.insert(en[i]);
			useful[en[i]]=false;
		}
	}
	for(int i=0;i<K;i++)
	{
		if(!useful[i])
			can_rm[i].push_back(-1);
		okrm2.insert(i);
	}
	for(int i=0;i<N;i++)
	{
		if(nokrm2.find(C[i])!=nokrm2.end())
		{
			nokrm2.erase(C[i]);
			okrm2.insert(C[i]);
			continue;
		}
		else if(okrm2.find(C[i])!=okrm2.end())
			continue;
		while(true)
		{
			int v=(*okrm2.begin());
			okrm2.erase(v);
			if(can_rm[v].back()<i)
			{
				WriteAdvice(1);
				can_rm[v].pop_back();
				break;
			}
			WriteAdvice(0);
			nokrm2.insert(v);
		}
		okrm2.insert(C[i]);
	}
	return;
}

assistant

#include<bits/stdc++.h>
#include "assistant.h"
#define fi first
#define se second
using namespace std;
const int NN=1e5;
set<int> okrm;
set<int> nokrm;
void Assist(unsigned char *A,int N,int K,int R)
{
	//for(int i=0;i<R;i++)
	//	cerr<<(int)A[i]<<" ";
	//cerr<<"\n";
	int it=0;
	for(int i=0;i<K;i++)
		okrm.insert(i);
	for(int qi=1;qi<=N;qi++)
	{
		int x=GetRequest();
		if(nokrm.find(x)!=nokrm.end())
		{
			nokrm.erase(x);
			okrm.insert(x);
			continue;
		}
		else if(okrm.find(x)!=okrm.end())
			continue;
		// must put back
		for(;A[it]==0;it++)
		{
			nokrm.insert(*okrm.begin());
			okrm.erase(okrm.begin());
		}
		it++;
		PutBack(*okrm.begin());
		okrm.erase(okrm.begin());
		okrm.insert(x);
	}
	return;
}

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