oj.uz

Submission #138724

# Submission time Handle Problem Language Result Execution time Memory
138724 2019-07-30T09:12:21 Z mahmoudbadawy Last supper (IOI12_supper) C++17
0 / 100
 270 ms 27120 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int NN=1e5+5;

vector<int> id[NN];
set< pair<int,pair<int,int> > > ss;
int cur[NN],isin[NN];
int sind[NN];
int adv[2*NN];

void ComputeAdvice(int *C, int N, int K, int M) {

	//WriteAdvice(0);
	for(int i=0;i<N;i++)
		id[C[i]].push_back(i);
	for(int i=0;i<N;i++)
		id[i].push_back(N+5);
	for(int i=0;i<K;i++)
	{
		ss.insert({-id[C[i]][0],{i,i}});
		sind[i]=i;
		isin[i]=1;
	}

	for(int i=0;i<N;i++)
	{
		if(isin[C[i]])
		{
			//cout << C[i] << " " << isin[C[i]] << " " << sind[C[i]] << endl;
			adv[sind[C[i]]]=1;
			ss.erase({-id[C[i]][cur[C[i]]],{sind[i],C[i]}});
			cur[C[i]]++;
			sind[C[i]]=i+K;
			ss.insert({-id[C[i]][cur[C[i]]],{sind[i],C[i]}});
		}
		else
		{
			//cout << C[i] << endl;
			auto del=*ss.begin();
			isin[del.S.S]=0;
			//cout << del.S.F << " " << del.S.S << endl;
			ss.erase(del);
			cur[C[i]]++;
			sind[C[i]]=i+K;
			isin[C[i]]=1;
			ss.insert({-id[C[i]][cur[C[i]]],{sind[i],C[i]}});
		}
	}
	for(int i=0;i<N+K;i++)
	{
		//cout << adv[i] << " ";
		WriteAdvice(adv[i]);
	}
}

#include "assistant.h"
#include <bits/stdc++.h>

using namespace std;

const int NN=1e5+5;

int in[NN],st[NN];
set< pair<int,int> > s2;

void Assist(unsigned char *A, int N, int K, int R) {

	for(int i=0;i<K;i++)
	{
		s2.insert({A[i],i});
		in[i]=1; st[i]=A[i];
	}
	for(int i=0;i<N;i++)
	{
		int x=GetRequest();
		if(in[x])
		{
			s2.erase({st[x],x});
			s2.insert({A[i+K],x});
			st[x]=A[i+K];
		}
		else
		{
			auto cur=(*s2.begin()).second;
			PutBack(cur);
			in[cur]=0;
			s2.erase(s2.begin());
			s2.insert({A[i+K],x});
			in[x]=1; st[x]=A[i+K];
		}
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5360 KB Output is correct
2 Incorrect 6 ms 5360 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 20 ms 7408 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 170 ms 22440 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 6128 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 206 ms 25328 KB Output isn't correct - not an optimal way
2 Incorrect 208 ms 26000 KB Output isn't correct - not an optimal way
3 Incorrect 214 ms 27120 KB Output isn't correct - not an optimal way
4 Incorrect 221 ms 26808 KB Output isn't correct - not an optimal way
5 Incorrect 217 ms 26864 KB Output isn't correct - not an optimal way
6 Incorrect 266 ms 26808 KB Output isn't correct - not an optimal way
7 Incorrect 270 ms 26808 KB Output isn't correct - not an optimal way
8 Incorrect 239 ms 27040 KB Output isn't correct - not an optimal way
9 Incorrect 216 ms 26864 KB Output isn't correct - not an optimal way
10 Incorrect 194 ms 24304 KB Output isn't correct - not an optimal way