oj.uz

Submission #698506

# Submission time Handle Problem Language Result Execution time Memory
698506 2023-02-13T16:10:55 Z arneves Last supper (IOI12_supper) C++17
100 / 100
 234 ms 76124 KB 
/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
	       .      .           .      .           .      .    	
	       _\/  \/_           _\/  \/_           _\/  \/_    	
	        _\/\/_             _\/\/_             _\/\/_     	
	    _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
	     / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
	        _/\/\_             _/\/\_             _/\/\_     	
	        /\  /\             /\  /\             /\  /\     	
	       '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

#include "advisor.h"

void ComputeAdvice(int *C, int N, int K, int M) {
	
	vector<deque<int> > times(N, deque<int>());
	
	for(int i=0; i<N; i++){
		times[C[i]].push_back(i);
	}
	
	for(int i=0; i<N; i++){
		times[i].push_back(1e6);
	}
	
	priority_queue<pair<int,int> > q;
	set<int> d;
	
	for(int i=0; i<K; i++){
		d.insert(i);
		q.push({times[i].front(),i});
	}
	
	vector<int> ans(2*N,0);
	vector<int> last(2*N,0);
	
	for(int i=0; i<K; i++) last[i]=i;
	
	for(int i=0; i<N; i++){
		times[C[i]].pop_front();
		if(d.find(C[i])==d.end()){
			d.insert(C[i]);
			
			int y=q.top().second; q.pop();
			while(d.find(y)==d.end()){
				y=q.top().second; q.pop();
			}
			d.erase(y);
			
			ans[last[y]]=1;
		}
		last[C[i]]=i+N;
		
		d.insert(C[i]);
		q.push({times[C[i]].front(),C[i]});
	}
	
	for(int u: ans) WriteAdvice(u);
}

/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
	       .      .           .      .           .      .    	
	       _\/  \/_           _\/  \/_           _\/  \/_    	
	        _\/\/_             _\/\/_             _\/\/_     	
	    _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
	     / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
	        _/\/\_             _/\/\_             _/\/\_     	
	        /\  /\             /\  /\             /\  /\     	
	       '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

#include "assistant.h"

void Assist(unsigned char *A, int N, int K, int R) {
	
	set<int> s;
	set<int> h;
	
	for(int i=0; i<K; i++){
		s.insert(i);
		if(A[i]==1) h.insert(i);
	}
	
	for (int i = 0; i < N; i++) {
		int req = GetRequest();
		
		if(s.find(req)==s.end()){
			int y=*(h.begin());
			h.erase(y);
			
			PutBack(y);
			s.erase(y);
		}
		if(A[i+N]) h.insert(req);
		s.insert(req);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 516 KB Output is correct
2 Correct 0 ms 644 KB Output is correct
3 Correct 3 ms 1420 KB Output is correct
4 Correct 4 ms 2724 KB Output is correct
5 Correct 6 ms 4148 KB Output is correct
6 Correct 9 ms 4204 KB Output is correct
7 Correct 7 ms 4284 KB Output is correct
8 Correct 8 ms 4284 KB Output is correct
9 Correct 10 ms 4324 KB Output is correct
10 Correct 11 ms 4412 KB Output is correct
11 Correct 9 ms 4276 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8052 KB Output is correct
2 Correct 97 ms 37352 KB Output is correct
3 Correct 221 ms 76124 KB Output is correct
4 Correct 171 ms 71764 KB Output is correct
5 Correct 187 ms 71980 KB Output is correct
6 Correct 204 ms 72712 KB Output is correct
7 Correct 212 ms 74756 KB Output is correct
8 Correct 183 ms 63596 KB Output is correct
9 Correct 130 ms 70428 KB Output is correct
10 Correct 225 ms 75764 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 60160 KB Output is correct
2 Correct 218 ms 75112 KB Output is correct
3 Correct 225 ms 75352 KB Output is correct
4 Correct 212 ms 75272 KB Output is correct
5 Correct 204 ms 74312 KB Output is correct
6 Correct 215 ms 75244 KB Output is correct
7 Correct 215 ms 75228 KB Output is correct
8 Correct 205 ms 74460 KB Output is correct
9 Correct 193 ms 75604 KB Output is correct
10 Correct 219 ms 75308 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3632 KB Output is correct
2 Correct 9 ms 4304 KB Output is correct
3 Correct 7 ms 4308 KB Output is correct
4 Correct 8 ms 4164 KB Output is correct
5 Correct 8 ms 4184 KB Output is correct
6 Correct 10 ms 4160 KB Output is correct
7 Correct 9 ms 4308 KB Output is correct
8 Correct 9 ms 4312 KB Output is correct
9 Correct 9 ms 4408 KB Output is correct
10 Correct 9 ms 4724 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 74688 KB Output is correct - 200000 bits used
2 Correct 231 ms 75008 KB Output is correct - 200000 bits used
3 Correct 219 ms 75264 KB Output is correct - 200000 bits used
4 Correct 230 ms 75216 KB Output is correct - 200000 bits used
5 Correct 234 ms 75208 KB Output is correct - 200000 bits used
6 Correct 230 ms 75124 KB Output is correct - 200000 bits used
7 Correct 224 ms 75120 KB Output is correct - 199678 bits used
8 Correct 226 ms 75164 KB Output is correct - 200000 bits used
9 Correct 231 ms 75240 KB Output is correct - 200000 bits used
10 Correct 213 ms 74384 KB Output is correct - 200000 bits used