제출 #567257

#제출 시각아이디문제언어결과실행 시간메모리
567257hibiki즐거운 행로 (APIO20_fun)C++11
66 / 100
291 ms21036 KiB
#include "fun.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define f first #define s second int n,q,mid; int dist[100005]; vector<int> head,sz,ans; vector<int> nh[3]; int fi_mid() { pair<int,int> mn = {1e9, -1}; for(int i = 0; i < n; i++) { int ret = attractionsBehind(0, i); if(ret > n / 2) mn = min(mn, {ret, i}); } return mn.s; } void fi_dist() { for(int i = 0; i < n; i++) { if(i == mid) dist[i] = 0; else dist[i] = hoursRequired(i, mid); if(dist[i] == 1) { head.pb(i); sz.pb(n - attractionsBehind(i, mid)); nh[head.size() - 1].pb(i); } } } void fi_nh() { for(int i = 0; i < n; i++) { if(i == mid || dist[i] == 1) continue; int ask0 = attractionsBehind(i, head[0]); int ask1 = attractionsBehind(i, head[1]); if(ask0 != sz[0]) nh[0].pb(i); else if(ask1 != sz[1]) nh[1].pb(i); else nh[2].pb(i); } } vector<int> createFunTour(int N, int Q) { n = N, q = Q; mid = fi_mid(); fi_dist(); fi_nh(); int prev = -1, ord[3] = {0, 1, 2}; for(int i = 0; i < 3; i++) sort(nh[i].begin(),nh[i].end(), [&](int x,int y) { return dist[x] < dist[y]; }); sort(ord, ord + 3, [&](int x,int y) { return nh[x].size() > nh[y].size(); }); while(nh[ord[0]].size() < nh[ord[1]].size() + nh[ord[2]].size()) { sort(ord, ord + 3, [&](int x,int y) { return dist[nh[x].back()] > dist[nh[y].back()]; }); int cur = (prev == ord[0]); ans.pb(nh[ord[cur]].back()); nh[ord[cur]].pop_back(); prev = ord[cur]; sort(ord, ord + 3, [&](int x,int y) { return nh[x].size() > nh[y].size(); }); } for(auto val: nh[ord[2]]) nh[ord[1]].pb(val); sort(nh[ord[1]].begin(),nh[ord[1]].end(), [&](int x,int y) { return dist[x] < dist[y]; }); nh[ord[2]].clear(); int cur = 0; while(nh[ord[cur]].size()) { ans.pb(nh[ord[cur]].back()); nh[ord[cur]].pop_back(); cur = 1 - cur; } ans.pb(mid); return ans; }
#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...