oj.uz

Submission #341929

# Submission time Handle Problem Language Result Execution time Memory
341929 2020-12-31T13:38:25 Z ogibogi2004 Last supper (IOI12_supper) C++14
100 / 100
 372 ms 24972 KB 
#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]);
	}
}

#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7300 KB Output is correct
2 Correct 4 ms 7016 KB Output is correct
3 Correct 7 ms 7152 KB Output is correct
4 Correct 9 ms 7440 KB Output is correct
5 Correct 11 ms 7472 KB Output is correct
6 Correct 13 ms 7484 KB Output is correct
7 Correct 13 ms 7508 KB Output is correct
8 Correct 16 ms 8028 KB Output is correct
9 Correct 15 ms 7600 KB Output is correct
10 Correct 17 ms 7860 KB Output is correct
11 Correct 16 ms 7728 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8236 KB Output is correct
2 Correct 119 ms 11208 KB Output is correct
3 Correct 358 ms 24972 KB Output is correct
4 Correct 182 ms 16068 KB Output is correct
5 Correct 205 ms 16376 KB Output is correct
6 Correct 259 ms 17604 KB Output is correct
7 Correct 319 ms 20248 KB Output is correct
8 Correct 296 ms 21492 KB Output is correct
9 Correct 139 ms 11948 KB Output is correct
10 Correct 372 ms 22852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 17660 KB Output is correct
2 Correct 330 ms 21264 KB Output is correct
3 Correct 338 ms 21656 KB Output is correct
4 Correct 329 ms 21292 KB Output is correct
5 Correct 282 ms 18876 KB Output is correct
6 Correct 346 ms 21720 KB Output is correct
7 Correct 327 ms 21592 KB Output is correct
8 Correct 354 ms 23836 KB Output is correct
9 Correct 239 ms 19796 KB Output is correct
10 Correct 347 ms 21832 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7572 KB Output is correct
2 Correct 16 ms 7856 KB Output is correct
3 Correct 11 ms 7344 KB Output is correct
4 Correct 12 ms 7628 KB Output is correct
5 Correct 12 ms 7344 KB Output is correct
6 Correct 14 ms 7344 KB Output is correct
7 Correct 15 ms 7824 KB Output is correct
8 Correct 15 ms 7728 KB Output is correct
9 Correct 15 ms 7728 KB Output is correct
10 Correct 18 ms 8396 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 19412 KB Output is correct - 120000 bits used
2 Correct 335 ms 19928 KB Output is correct - 122000 bits used
3 Correct 336 ms 20664 KB Output is correct - 125000 bits used
4 Correct 331 ms 20628 KB Output is correct - 125000 bits used
5 Correct 355 ms 20828 KB Output is correct - 125000 bits used
6 Correct 351 ms 20424 KB Output is correct - 125000 bits used
7 Correct 340 ms 20636 KB Output is correct - 124828 bits used
8 Correct 335 ms 20584 KB Output is correct - 124910 bits used
9 Correct 327 ms 20624 KB Output is correct - 125000 bits used
10 Correct 363 ms 22572 KB Output is correct - 125000 bits used