Submission #567966

#TimeUsernameProblemLanguageResultExecution timeMemory
567966hhhhauraFun Tour (APIO20_fun)C++14
0 / 100
1 ms256 KiB
#include "fun.h" #define wiwihorz #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("sse") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i ++) #define rrep(i, a, b) for(int i = b; i >= a; i --) #define all(x) x.begin(), x.end() #define ceil(a, b) ((a + b - 1) / (b)) #define ll long long int #define lld long double #define pii pair<int, int> #define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()) #define INF 2000000000 #define MOD 1000000007 #define eps (1e-9) using namespace std; #ifdef wiwihorz #define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a) void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; } void kout() { cerr << endl; } template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);} #else #define print(...) 0 #define vprint(...) 0 #endif vector<int> createFunTour(int N, int Q) { if(N == 2) return {0, 1}; vector<int> sz(N, 0), dis(N, 0), id(N, -1); vector<vector<int>> v(3, vector<int>()); int cen = 0, best = N; rep(i, 1, N - 1) { sz[i] = attractionsBehind(0, i); if(sz[i] * 2 >= N && best > sz[i]) { cen = i, best = sz[i]; } } vector<int> up; rep(i, 0, N - 1) if(cen != i) { dis[i] = hoursRequired(cen, i); if(dis[i] == 1) up.push_back(i); } rep(i, 0, N - 1) if(i != cen) { int L = hoursRequired(up[0], i); int R = hoursRequired(up[1], i); if(L + 1 == dis[i]) v[0].push_back(i); else if(R + 1 == dis[i]) v[1].push_back(i); else v[2].push_back(i); } vector<int> L, R, ans; print(up.size()); if(up.size() == 3) { vector<int> piv(3, 0); int a = v[0].size(), b = v[1].size(), c = v[2].size(); rep(i, 0, 2) { sort(all(v[i]), [&](int x, int y) { return dis[x] > dis[y]; }); } int pre = -1, cur = 0, tot = 0; while(max({a - piv[0], b - piv[1], c - piv[2]}) * 2 < a + b + c - tot) { cur = (pre + 1) % 3; rep(i, 0, 2) if(i != pre) { if(dis[v[i][piv[i]]] > dis[v[cur][piv[cur]]]) cur = i; } tot ++, pre = cur; ans.push_back(v[cur][piv[cur] ++]); } rep(i, 1, 2) if(v[i].size() - piv[i] > v[0].size() - piv[0]) swap(v[0], v[i]); rep(i, piv[0], v[0].size() - 1) L.push_back(v[0][i]); rep(i, piv[1], v[1].size() - 1) R.push_back(v[1][i]); rep(i, piv[2], v[2].size() - 1) R.push_back(v[2][i]); } else L = v[0], R = v[1]; if(L.size() < R.size()) swap(L, R); sort(all(R), [&](int x, int y) { return dis[x] > dis[y]; }); sort(all(L), [&](int x, int y) { return dis[x] > dis[y]; }); int l = 0, r = 0; while(l < L.size()) { ans.push_back(L[l++]); if(r < R.size()) ans.push_back(R[r++]); } ans.push_back(cen); return ans; }

Compilation message (stderr)

fun.cpp:6: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    6 | #pragma loop-opt(on)
      | 
fun.cpp:21:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
fun.cpp:21:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(int i = a; i <= b; i ++)
......
   73 |   rep(i, piv[0], v[0].size() - 1) L.push_back(v[0][i]);
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~       
fun.cpp:73:3: note: in expansion of macro 'rep'
   73 |   rep(i, piv[0], v[0].size() - 1) L.push_back(v[0][i]);
      |   ^~~
fun.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(int i = a; i <= b; i ++)
......
   74 |   rep(i, piv[1], v[1].size() - 1) R.push_back(v[1][i]);
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~       
fun.cpp:74:3: note: in expansion of macro 'rep'
   74 |   rep(i, piv[1], v[1].size() - 1) R.push_back(v[1][i]);
      |   ^~~
fun.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(int i = a; i <= b; i ++)
......
   75 |   rep(i, piv[2], v[2].size() - 1) R.push_back(v[2][i]);
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~       
fun.cpp:75:3: note: in expansion of macro 'rep'
   75 |   rep(i, piv[2], v[2].size() - 1) R.push_back(v[2][i]);
      |   ^~~
fun.cpp:86:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while(l < L.size()) {
      |        ~~^~~~~~~~~~
fun.cpp:88:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   if(r < R.size()) ans.push_back(R[r++]);
      |      ~~^~~~~~~~~~
#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...