제출 #812650

#제출 시각아이디문제언어결과실행 시간메모리
812650Hanksburger즐거운 행로 (APIO20_fun)C++17
21 / 100
439 ms93924 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; int ok[100005], depth[100005], n; set<pair<int, int> > s[100005]; vector<int> ans; void dfs(int u) { s[u].insert({-depth[u], u}); if (u*2+1<n) { depth[u*2+1]=depth[u]+1; dfs(u*2+1); s[u].insert(s[u*2+1].begin(), s[u*2+1].end()); } if (u*2+2<n) { depth[u*2+2]=depth[u]+1; dfs(u*2+2); s[u].insert(s[u*2+2].begin(), s[u*2+2].end()); } } vector<int> createFunTour(int nn, int qq) { n=nn; dfs(0); for (int i=0; i<n; i++) ok[i]=1; int cur=n-1; ok[cur]=0; ans.push_back(cur); { int u=cur; while (u) { s[u].erase({-depth[cur], cur}); u=(u-1)/2; } s[u].erase({-depth[cur], cur}); } for (int i=1; i<n; i++) { int u=cur, cnt=1, mx=0, ind; while (u) { cnt++; if (u&1 && ok[u+1]) { if (mx<cnt-depth[u+1]-(*s[u+1].begin()).first) { mx=cnt-depth[u+1]-(*s[u+1].begin()).first; ind=(*s[u+1].begin()).second; } } else if (u%2==0 && ok[u-1]) { if (mx<cnt-depth[u-1]-(*s[u-1].begin()).first) { mx=cnt-depth[u-1]-(*s[u-1].begin()).first; ind=(*s[u-1].begin()).second; } } u=(u-1)/2; } if (mx) cur=ind; else cur=(cur-1)/2; ok[cur]=0; ans.push_back(cur); { int u=cur; while (u) { s[u].erase({-depth[cur], cur}); u=(u-1)/2; } s[u].erase({-depth[cur], cur}); } } 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...