제출 #565197

#제출 시각아이디문제언어결과실행 시간메모리
565197ngpin04즐거운 행로 (APIO20_fun)C++14
0 / 100
2 ms340 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #include "fun.h" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int Nmax = 1e5 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); #define asksz attractionsBehind #define askdis hoursRequired vector <int> s[10]; int comp[Nmax]; int sz[Nmax]; int d[Nmax]; int n,q; vector<int> createFunTour(int N, int Q) { n = N; q = Q; if (n == 2) return vector <int> {0, 1}; int cen = 0; int minsz = n; for (int i = 1; i < n; i++) { sz[i] = asksz(0, i); if (2 * sz[i] >= n) { if (mini(minsz, sz[i])) cen = i; } } vector <int> cand; for (int i = 0; i < n; i++) { d[i] = askdis(cen, i); if (d[i] == 1) cand.push_back(i); } assert(cand.size() > 1); sort(ALL(cand), [](int i, int j) { return sz[i] < sz[j]; }); for (int i = 0; i < n; i++) if (i != cen) { int comp = 2; for (int j = 0; j < 2; j++) if (askdis(cand[j], i) + 1 == d[i]) comp = j; s[comp].push_back(i); } for (int i = 0; i < 3; i++) { sort(ALL(s[i]), [](int i, int j) { return d[i] < d[j]; }); } vector <int> res; if (cand.size() == 3) { int las = -1; while (true) { for (int i = 0; i < 3; i++) for (int j = i + 1; j < 3; j++) if (s[i].size() > s[j].size()) swap(s[i], s[j]); if (s[0].size() + s[1].size() == s[2].size()) break; int maxd = 0; int mx = -1; for (int i = 0; i < 3; i++) if (i != las && s[i].size()) { if (maxi(maxd, d[s[i].back()])) mx = i; } assert(mx >= 0); res.push_back(s[mx].back()); las = mx; s[mx].pop_back(); } for (int x : s[1]) s[0].push_back(x); sort(ALL(s[0]), [](int i, int j) { return d[i] < d[j]; }); s[1] = s[2]; if (las != 2) swap(s[0], s[1]); } if (s[1].size() > s[0].size()) { res.push_back(s[1].back()); s[1].pop_back(); } while (s[0].size()) { for (int i = 0; i < 2; i++) { res.push_back(s[i].back()); s[i].pop_back(); } } res.push_back(cen); return res; } //#include "grader.cpp"
#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...