Submission #698506

#TimeUsernameProblemLanguageResultExecution timeMemory
698506arnevesLast supper (IOI12_supper)C++17
100 / 100
234 ms76124 KiB
/* ______ _____ _______ _ _ _______ __ _ _____ _ _ _ |_____/ | | | |____/ |______ | \ | | | | | | | \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__| . . . . . . _\/ \/_ _\/ \/_ _\/ \/_ _\/\/_ _\/\/_ _\/\/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_ / /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \ _/\/\_ _/\/\_ _/\/\_ /\ /\ /\ /\ /\ /\ ' ' ' ' ' ' */ #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); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...