oj.uz

Submission #349828

# Submission time Handle Problem Language Result Execution time Memory
349828 2021-01-18T13:13:20 Z juggernaut Last supper (IOI12_supper) C++14
100 / 100
 153 ms 73844 KB 
//Powered by official solution
#include<bits/stdc++.h>
#include"advisor.h"
using namespace std;
int const MAXN=100000;
struct Color{
	int id;
	int np;
	Color(){}
	Color(int _id,int _np){
		id=_id;
		np=_np;
	}
};
bool operator<(Color const &a,Color const &b){
	return(a.np<b.np);
}
int nxt[MAXN];
int position[MAXN];
bool in_scaffold[MAXN];
priority_queue<Color>coda;
int solution[MAXN];
queue<int>events[MAXN];
int accumulated=0;
int counter=0;
void ComputeAdvice(int *d,int n,int k,int m){
	for(int i=0;i<n;i++)position[i]=n;
	for(int i=n-1;i>=0;i--)nxt[i]=position[d[i]],position[d[i]]=i;
	for(int j=0;j<k;j++){
		in_scaffold[j]=1;
		coda.push(Color(j,position[j]));
	}
	for(int i=0;i<n;i++){
		int color=d[i];
		if(in_scaffold[color]){
			coda.push(Color(color,nxt[i]));
			solution[i]=-1;
			events[color].push(1);
			continue;
		}		
		Color useless=coda.top();
		coda.pop();
		in_scaffold[useless.id]=0;
		coda.push(Color(color,nxt[i]));
		in_scaffold[color]=1;
		solution[i]=useless.id;
		events[useless.id].push(0);
		events[color].push(1);
	}
	for(int j=0;j<k;j++){
		if(events[j].empty()){
			WriteAdvice(0);
			continue;
		}
		if(events[j].front()==0){
			events[j].pop();
			WriteAdvice(0);
		}else WriteAdvice(1);
	}
	for(int i=0;i<n;i++){	
		int color=d[i];
		assert(events[color].front()==1);
		events[color].pop();
		if(events[color].empty()){
			WriteAdvice(0);
			continue;
		}
		if(events[color].front()==0){
			events[color].pop();
		    WriteAdvice(0);
		}else WriteAdvice(1);
	}
}
//Powered by official solution
#include<bits/stdc++.h>
#include"assistant.h"
using namespace std;
int const MAXN=100000;
bool in_the_scaffold[MAXN];
queue<int>passive;
void Assist(unsigned char *real_advice,int n,int k,int l){
	for(int i=0;i<k;i++){
		in_the_scaffold[i]=1;
		if(real_advice[i]==0)passive.push(i);
	}
	for(int i=0;i<n;i++){
		int color=GetRequest();
		if (!in_the_scaffold[color]){
			in_the_scaffold[passive.front()]=0;
			in_the_scaffold[color]=1;
			PutBack(passive.front());
			passive.pop();	
		}
		if(real_advice[k+i]==0)passive.push(color);
	}	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 68072 KB Output is correct
2 Correct 51 ms 68200 KB Output is correct
3 Correct 51 ms 68376 KB Output is correct
4 Correct 51 ms 68232 KB Output is correct
5 Correct 54 ms 68516 KB Output is correct
6 Correct 54 ms 68384 KB Output is correct
7 Correct 57 ms 68916 KB Output is correct
8 Correct 56 ms 68384 KB Output is correct
9 Correct 54 ms 68428 KB Output is correct
10 Correct 58 ms 68612 KB Output is correct
11 Correct 57 ms 68256 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 68764 KB Output is correct
2 Correct 91 ms 70924 KB Output is correct
3 Correct 147 ms 73588 KB Output is correct
4 Correct 144 ms 72456 KB Output is correct
5 Correct 144 ms 72616 KB Output is correct
6 Correct 143 ms 72848 KB Output is correct
7 Correct 145 ms 73292 KB Output is correct
8 Correct 133 ms 72508 KB Output is correct
9 Correct 130 ms 72896 KB Output is correct
10 Correct 145 ms 73772 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 72520 KB Output is correct
2 Correct 148 ms 73268 KB Output is correct
3 Correct 148 ms 73496 KB Output is correct
4 Correct 145 ms 73396 KB Output is correct
5 Correct 138 ms 73380 KB Output is correct
6 Correct 145 ms 73308 KB Output is correct
7 Correct 146 ms 73432 KB Output is correct
8 Correct 148 ms 73020 KB Output is correct
9 Correct 147 ms 73536 KB Output is correct
10 Correct 144 ms 73520 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 68248 KB Output is correct
2 Correct 57 ms 68584 KB Output is correct
3 Correct 54 ms 68384 KB Output is correct
4 Correct 54 ms 68456 KB Output is correct
5 Correct 57 ms 68256 KB Output is correct
6 Correct 58 ms 68384 KB Output is correct
7 Correct 59 ms 68564 KB Output is correct
8 Correct 58 ms 68384 KB Output is correct
9 Correct 59 ms 68384 KB Output is correct
10 Correct 59 ms 68392 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 73748 KB Output is correct - 120000 bits used
2 Correct 145 ms 73496 KB Output is correct - 122000 bits used
3 Correct 144 ms 73608 KB Output is correct - 125000 bits used
4 Correct 145 ms 73708 KB Output is correct - 125000 bits used
5 Correct 153 ms 73612 KB Output is correct - 125000 bits used
6 Correct 147 ms 73844 KB Output is correct - 125000 bits used
7 Correct 146 ms 73480 KB Output is correct - 124828 bits used
8 Correct 143 ms 73708 KB Output is correct - 124910 bits used
9 Correct 147 ms 73608 KB Output is correct - 125000 bits used
10 Correct 147 ms 73428 KB Output is correct - 125000 bits used