Submission #568030

#	Time	Username	Problem	Language	Result	Execution time	Memory
568030		hhhhaura	Fun Tour (APIO20_fun)	C++14	100 / 100	398 ms	22196 KiB

fun

#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), up;
	vector<vector<int>> v(3, vector<int>());
	int cen = 0, best = N, bad = -1;
	rep(i, 1, N - 1) {
		sz[i] = attractionsBehind(0, i);
		if(sz[i] * 2 >= N && best >= sz[i]) {
			cen = i, best = sz[i];
		} 
	}
	auto cmp = [&](int x, int y) {
		if(dis[x] != dis[y]) return dis[x] > dis[y];
		else return (id[x] != bad) > (id[y] != bad);
	};
	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), id[i] = 0;
		else if(R + 1 == dis[i]) v[1].push_back(i), id[i] = 1;
		else v[2].push_back(i), id[i] = 2;
	}
	vector<int> L, R, ans;
	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]), cmp);
		int pre = -1, cur = 0, tot = 0;
		while(max({a - piv[0], b - piv[1], c - piv[2]})* 2 < a + b + c - tot) {
			cur = -1;
			rep(i, 0, 2) if(i != pre && piv[i] < v[i].size()) {
				if(cur == -1 || dis[v[i][piv[i]]] 
					> dis[v[cur][piv[cur]]]) cur = i;
			}
			tot ++, pre = cur;
			ans.push_back(v[cur][piv[cur] ++]);
		}
		int ok = 0;
		rep(i, 1, 2) if(v[i].size() - piv[i] 
			> v[ok].size() - piv[ok]) ok = i;
		bad = pre;
		rep(i, piv[ok], v[ok].size() - 1) L.push_back(v[ok][i]);
		rep(j, 0, 2) if(j != ok)
			rep(i, piv[j], v[j].size() - 1) R.push_back(v[j][i]);
		sort(all(R), cmp);
		if(dis[R[0]] > dis[L[0]] && id[R[0]] != pre) swap(L, R);
	}
	else L = v[0], R = v[1];
	if(L.size() < R.size()) swap(L, R);
	sort(all(R), cmp);
	sort(all(L), cmp);
	int l = 0, r = 0;
	while(l < L.size()) {
		if(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:62:39: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    rep(i, 0, 2) if(i != pre && piv[i] < v[i].size()) {
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[ok], v[ok].size() - 1) L.push_back(v[ok][i]);
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~     
fun.cpp:73:3: note: in expansion of macro 'rep'
   73 |   rep(i, piv[ok], v[ok].size() - 1) L.push_back(v[ok][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[j], v[j].size() - 1) R.push_back(v[j][i]);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~      
fun.cpp:75:4: note: in expansion of macro 'rep'
   75 |    rep(i, piv[j], v[j].size() - 1) R.push_back(v[j][i]);
      |    ^~~
fun.cpp:84:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  while(l < L.size()) {
      |        ~~^~~~~~~~~~
fun.cpp:85:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if(l < L.size()) ans.push_back(L[l++]);
      |      ~~^~~~~~~~~~
fun.cpp:86:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   if(r < R.size()) ans.push_back(R[r++]);
      |      ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 34 / 34