oj.uz

Submission #401815

# Submission time Handle Problem Language Result Execution time Memory
401815 2021-05-10T21:16:21 Z Jasiekstrz Last supper (IOI12_supper) C++17
100 / 100
 273 ms 17260 KB 
#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;
}


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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2944 KB Output is correct
2 Correct 4 ms 2948 KB Output is correct
3 Correct 4 ms 3184 KB Output is correct
4 Correct 6 ms 3084 KB Output is correct
5 Correct 10 ms 3164 KB Output is correct
6 Correct 9 ms 3372 KB Output is correct
7 Correct 8 ms 3368 KB Output is correct
8 Correct 11 ms 3488 KB Output is correct
9 Correct 11 ms 3500 KB Output is correct
10 Correct 12 ms 3628 KB Output is correct
11 Correct 11 ms 3500 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4048 KB Output is correct
2 Correct 95 ms 6712 KB Output is correct
3 Correct 273 ms 17260 KB Output is correct
4 Correct 115 ms 9912 KB Output is correct
5 Correct 146 ms 10000 KB Output is correct
6 Correct 189 ms 11356 KB Output is correct
7 Correct 236 ms 13696 KB Output is correct
8 Correct 187 ms 14432 KB Output is correct
9 Correct 104 ms 8604 KB Output is correct
10 Correct 246 ms 15740 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 12372 KB Output is correct
2 Correct 244 ms 14612 KB Output is correct
3 Correct 249 ms 15052 KB Output is correct
4 Correct 242 ms 14660 KB Output is correct
5 Correct 231 ms 13108 KB Output is correct
6 Correct 243 ms 14828 KB Output is correct
7 Correct 248 ms 14852 KB Output is correct
8 Correct 217 ms 15792 KB Output is correct
9 Correct 235 ms 13924 KB Output is correct
10 Correct 250 ms 14808 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3484 KB Output is correct
2 Correct 10 ms 3472 KB Output is correct
3 Correct 8 ms 3132 KB Output is correct
4 Correct 8 ms 3252 KB Output is correct
5 Correct 8 ms 3252 KB Output is correct
6 Correct 9 ms 3212 KB Output is correct
7 Correct 11 ms 3400 KB Output is correct
8 Correct 11 ms 3524 KB Output is correct
9 Correct 11 ms 3492 KB Output is correct
10 Correct 12 ms 4040 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 13944 KB Output is correct - 92928 bits used
2 Correct 248 ms 14300 KB Output is correct - 91736 bits used
3 Correct 250 ms 14840 KB Output is correct - 88326 bits used
4 Correct 272 ms 14816 KB Output is correct - 88467 bits used
5 Correct 248 ms 14824 KB Output is correct - 87997 bits used
6 Correct 253 ms 14960 KB Output is correct - 88090 bits used
7 Correct 245 ms 14792 KB Output is correct - 87920 bits used
8 Correct 258 ms 14808 KB Output is correct - 88388 bits used
9 Correct 258 ms 14812 KB Output is correct - 88500 bits used
10 Correct 226 ms 15748 KB Output is correct - 99894 bits used