Submission #430058

#TimeUsernameProblemLanguageResultExecution timeMemory
430058PetiFun Tour (APIO20_fun)C++14
66 / 100
428 ms21040 KiB
#include <bits/stdc++.h> #include "fun.h" using namespace std; bool check(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int d){ return max(d, (v3.empty() ? 0 : v3.back().first)) >= max((v1.empty() ? 0 : v1.back().first), (v2.empty() ? 0 : v2.back().first)); } void combine(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int &last, int d){ if(v3.size() == 0) return; if(v1.size() + v2.size() <= v3.size() && (last == 3 || check(v1, v2, v3, d))){ for(auto p : v2) v1.push_back(p); sort(v1.begin(), v1.end()); swap(v2, v3); v3.clear(); if(last == 2) last = 1; else if(last == 3) last = 2; } else if(v1.size() + v3.size() <= v2.size() && (last == 2 || check(v1, v3, v2, d))){ for(auto p : v3) v1.push_back(p); sort(v1.begin(), v1.end()); v3.clear(); if(last == 3) last = 1; } else if(v2.size() + v3.size() <= v1.size() && (last == 1 || check(v2, v3, v1, d))){ for(auto p : v3) v2.push_back(p); sort(v2.begin(), v2.end()); v3.clear(); if(last == 3) last = 2; } } vector<int> createFunTour(int N, int Q) { int c = 0; for(int i = 1; i < N; i++){ int ans = attractionsBehind(c, i); if(ans*2 > N) c = i; } //cout<<"centroid: "<<c<<"\n"; vector<int> tavC(N), inds; for(int i = 0; i < N; i++){ tavC[i] = hoursRequired(c, i); if(tavC[i] == 1) inds.push_back(i); } if(inds.size() < 2) return {0, 1}; vector<int> tav1(N), tav2(N); for(int i = 0; i < N; i++) tav1[i] = hoursRequired(inds[0], i); for(int i = 0; i < N; i++) tav2[i] = hoursRequired(inds[1], i); vector<pair<int, int>> v1, v2, v3; for(int i = 0; i < N; i++){ if(tav1[i] < tav2[i] && tav1[i] < tavC[i]) v1.push_back(make_pair(tavC[i], i)); else if(tav2[i] < tav1[i] && tav2[i] < tavC[i]) v2.push_back(make_pair(tavC[i], i)); else v3.push_back(make_pair(tavC[i], i)); } sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); sort(v3.begin(), v3.end()); /*cout<<"csop1\n"; for(auto p : v1) cout<<p.first<<" "<<p.second<<"\n"; cout<<"csop2\n"; for(auto p : v2) cout<<p.first<<" "<<p.second<<"\n"; cout<<"csop3\n"; for(auto p : v3) cout<<p.first<<" "<<p.second<<"\n";*/ int last = 0, d = (int)1e9; combine(v1, v2, v3, last, d); if(v3.size() == 0){ last = 2; if(v2.size() > v1.size()) last = 1; } else{ last = 1; if(v2.back().first > v1.back().first) last = 2; if(v3.back().first > v2.back().first && v3.back().first > v1.back().first) last = 3; last++; if(last == 4) last = 1; } vector<int> ret; while(!v1.empty() || !v2.empty() || !v3.empty()){ if(v3.empty()){ if(last == 1){ if(v2.empty()) return ret; ret.push_back(v2.back().second); last = 2; v2.pop_back(); } else{ if(v1.empty()) return ret; ret.push_back(v1.back().second); last = 1; v1.pop_back(); } } else{ if(last == 1){ if(v2.empty() || v3.empty()) return {}; if(v2.back().first > v3.back().first){ ret.push_back(v2.back().second); last = 2; d = v2.back().first; v2.pop_back(); } else{ ret.push_back(v3.back().second); last = 3; d = v3.back().first; v3.pop_back(); } } else if(last == 2){ if(v2.empty() || v3.empty()) return {}; if(v1.back().first > v3.back().first){ ret.push_back(v1.back().second); last = 1; d = v1.back().first; v1.pop_back(); } else{ ret.push_back(v3.back().second); last = 3; d = v3.back().first; v3.pop_back(); } } else{ if(v1.empty() || v2.empty()) return {}; if(v1.back().first > v2.back().first){ ret.push_back(v1.back().second); last = 1; d = v1.back().first; v1.pop_back(); } else{ ret.push_back(v2.back().second); last = 2; d = v2.back().first; v2.pop_back(); } } combine(v1, v2, v3, last, d); } } return ret; }
#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...