Submission #341929

#	Time	Username	Problem	Language	Result	Execution time	Memory
341929		ogibogi2004	Last supper (IOI12_supper)	C++14	100 / 100	372 ms	24972 KiB

advisor

#include "advisor.h"
#include<bits/stdc++.h>
using namespace std;
#define floor sdfds
const int MAXN=2e5+6;
int nxt[MAXN],pr[MAXN];
bool on_floor[MAXN];
vector<int>v[MAXN];
set<pair<int,int> >floor;
bool t[MAXN];
void ComputeAdvice(int *C, int N, int K, int M) {
	vector<int>gg;
	for(int i=0;i<K;i++)
	{
		gg.push_back(i);
	}
	for(int i=0;i<N;i++)
	{
		gg.push_back(C[i]);
	}
	for(int i=0;i<gg.size();i++)
	{
		v[gg[i]].push_back(i);
	}
	memset(pr,-1,sizeof(pr));
	memset(nxt,-1,sizeof(nxt));
	for(int i=0;i<MAXN;i++)
	{
		for(int j=0;j<v[i].size();j++)
		{
			if(j!=0)pr[v[i][j]]=v[i][j-1];
			if(j!=v[i].size()-1)
			{
				nxt[v[i][j]]=v[i][j+1];
			}
		}
	}
	for(int i=0;i<gg.size();i++)
	{
		//cout<<"r "<<gg[i]<<endl;
		if(floor.size()<K)
		{
			if(nxt[i]!=-1)floor.insert({-nxt[i],i});
			else floor.insert({-MAXN,i});
			on_floor[gg[i]]=1;
		}
		else
		{
			if(on_floor[gg[i]])
			{
				t[pr[i]]=1;
				floor.erase({-i,pr[i]});
				if(nxt[i]!=-1)floor.insert({-nxt[i],i});
				else floor.insert({-MAXN,i});
			}
			else
			{
				auto p=(*floor.begin());
				floor.erase(p);
				//cout<<"p "<<gg[p.second]<<endl;
				on_floor[gg[p.second]]=0;
				on_floor[gg[i]]=1;
				if(nxt[i]!=-1)floor.insert({-nxt[i],i});
				else floor.insert({-MAXN,i});
			}
		}
	}
	//cout<<"e\n";
	for(int i=0;i<gg.size();i++)
	{
		WriteAdvice(t[i]);
	}
}

assistant

#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
set<pair<int,int> >scaffold;
set<int>s1;
map<int,int>mp;
set<pair<int,int> >for_removing;
int color[MAXN];
void Assist(unsigned char *A, int N, int K, int R) {
	for(int i=0;i<K;i++)
	{
		scaffold.insert({i,i});
		s1.insert(i);
		mp[i]=i;
		if(A[i]==0)
		{
			for_removing.insert({i,i});
		}
	}
	for(int i=0;i<N;i++)
	{
		int c=GetRequest();
		if(s1.find(c)!=s1.end())
		{
			scaffold.erase({mp[c],c});
			mp[c]=i+K;
			scaffold.insert({mp[c],c});
			if(A[i+K]==0)for_removing.insert({mp[c],c});
		}
		else
		{
			auto xd=(*for_removing.begin());
			s1.erase(xd.second);
			for_removing.erase(xd);
			PutBack(xd.second);
			scaffold.erase(xd);
			mp[c]=i;
			scaffold.insert({mp[c],c});
			if(A[i+K]==0)for_removing.insert({mp[c],c});
			s1.insert(c);
		}
	}
}

Compilation message (stderr)

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<gg.size();i++)
      |              ~^~~~~~~~~~
advisor.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int j=0;j<v[i].size();j++)
      |               ~^~~~~~~~~~~~
advisor.cpp:32:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    if(j!=v[i].size()-1)
      |       ~^~~~~~~~~~~~~~~
advisor.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0;i<gg.size();i++)
      |              ~^~~~~~~~~~
advisor.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   if(floor.size()<K)
      |                  ^
advisor.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<gg.size();i++)
      |              ~^~~~~~~~~~

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