Submission #466645

#	Time	Username	Problem	Language	Result	Execution time	Memory
466645		flappybird	Fun Tour (APIO20_fun)	C++14	100 / 100	282 ms	21432 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#include <cassert>

#define e(v) ( ( (v).empty() ) ? (pair<int, int>(-1, -1) ) : ( (v)[(v).size()-1] ) )

using namespace std;
typedef int ll;

vector<int> createFunTour(int N, int Q) {
	if (N == 2) {
		vector<ll> v;
		v.push_back(0);
		v.push_back(1);
		return v;
	}
	vector<ll> res;
	ll i;
	for (i = 0; i < N; i++) res.push_back(attractionsBehind(0, i));
	ll c = 0;
	ll mn = 1010101010;
	for (i = 0; i < N; i++) {
		if (res[i] >= (N + 1) / 2) {
			if (mn > res[i]) mn = res[i], c = i;
		}
	}
	vector<pair<ll, ll>> dis;
	vector<vector<pair<ll, ll>>> subtree;
	subtree.resize(3);
	ll num;
	for (i = 0; i < N; i++) {
		if (i == c) continue;
		dis.push_back({ hoursRequired(i, c), i });
	}
	sort(dis.begin(), dis.end());
	num = 1;
	subtree[0].push_back(dis[0]);
	for (i = 1; i < dis.size(); i++) {
		ll j;
		for (j = 0; j < num; j++) {
			if (j == 2) break;
			if (hoursRequired(dis[i].second, subtree[j][0].second) != dis[i].first + subtree[j][0].first) break;
		}
		if (j == num) num++;
		subtree[j].push_back(dis[i]);
	}
	vector<ll> ans;
	assert(num >= 2);
	if (num == 2) {
		ll r = N;
		ll a;
		if (subtree[0].size() < subtree[1].size()) a = 1;
		else a = 0;
		while (r != 1) {
			ans.push_back(e(subtree[a]).second);
			subtree[a].pop_back();
			a = !a;
			r--;
		}
		ans.push_back(c);
	}
	else {
		ll chk = 0;
		ll r = N;
		ll a;
		vector<ll> asdf(N);
		if (e(subtree[0]).first > e(subtree[1]).first) swap(subtree[0], subtree[1]);
		if (e(subtree[1]).first > e(subtree[2]).first) swap(subtree[1], subtree[2]);
		if (e(subtree[0]).first == e(subtree[1]).first && subtree[0].size() > subtree[1].size()) swap(subtree[0], subtree[1]);
		if (e(subtree[1]).first == e(subtree[2]).first && subtree[1].size() > subtree[2].size()) swap(subtree[1], subtree[2]);
		for (i = 0; i < 3; i++) {
			for (auto x : subtree[i]) {
				assert(!asdf[x.second]);
				asdf[x.second]++;
			}
		}
		for (i = 0; i < N; i++) {
			assert(asdf[i] <= 1);
		}
		a = 2;
		ll abc = c;
		ll memo = -1;
		ll chkchk = 0;
		if (2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= N - 1) {
			chk = 1;
			ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() });
			ll na = a;
			if (a != 0 && mx == subtree[0].size()) na = 0;
			if (a != 1 && mx == subtree[1].size()) na = 1;
			if (a != 2 && mx == subtree[2].size()) na = 2;
			memo = na;
			a = na;
			chkchk = 1;
		}
		while (r != 1) {
			ll b, c;
			b = a + 1;
			c = a + 2;
			b %= 3;
			c %= 3;
			ll loc = subtree[a][subtree[a].size() - 1].second;
			ll d = subtree[a][subtree[a].size() - 1].first;
			//assert(asdf[loc] == a);
			ans.push_back(loc);
			subtree[a].pop_back();
			if (chk || 2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= (r)-2) {
				chk = 1;
				ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() });
				ll na = a;
				if (a != 0 && mx == subtree[0].size()) na = 0;
				if (a != 1 && mx == subtree[1].size()) na = 1;
				if (a != 2 && mx == subtree[2].size()) na = 2;
				if (memo == -1) memo = na;
				if (memo == a) {
					if (subtree[b].empty() && subtree[c].empty()) {
						if (subtree[a].size()) ans.push_back(e(subtree[a]).second);
						ans.push_back(abc);
						assert(ans.size() == N);
						return ans;
					}
					if (e(subtree[b]).first < e(subtree[c]).first) a = c;
					else if (e(subtree[b]).first == e(subtree[c]).first && (subtree[b].size() < subtree[c].size())) a = c;
					else a = b;
				}
				else if (chkchk) a = memo;
				else if (memo == b) {
					chkchk = 1;
					if (d < e(subtree[c]).first) a = c;
					else a = b;
				}
				else {
					chkchk = 1;
					if (d < e(subtree[b]).first) a = b;
					else a = c;
				}
			}
			else {
				if (e(subtree[b]).first < e(subtree[c]).first) a = c;
				else if (e(subtree[b]).first == e(subtree[c]).first && (subtree[b].size() < subtree[c].size())) a = c;
				else a = b;
			}
			r--;
		}
		for (i = 0; i < ans.size(); i++) assert(ans[i] != c);
		ans.push_back(c);
	}
	vector<ll> asdfsdf(N);
	for (i = 0; i < N; i++) asdfsdf[ans[i]] = 1;
	for (i = 0; i < N; i++) assert(asdfsdf[i]);
	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:38:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (i = 1; i < dis.size(); i++) {
      |              ~~^~~~~~~~~~~~
fun.cpp:84:76: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   84 |   if (2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= N - 1) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
fun.cpp:88:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    if (a != 0 && mx == subtree[0].size()) na = 0;
      |                  ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:89:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    if (a != 1 && mx == subtree[1].size()) na = 1;
      |                  ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:90:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    if (a != 2 && mx == subtree[2].size()) na = 2;
      |                  ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:106:84: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'll' {aka 'int'} [-Wsign-compare]
  106 |    if (chk || 2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= (r)-2) {
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
fun.cpp:110:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     if (a != 0 && mx == subtree[0].size()) na = 0;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:111:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     if (a != 1 && mx == subtree[1].size()) na = 1;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:112:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     if (a != 2 && mx == subtree[2].size()) na = 2;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from fun.cpp:3:
fun.cpp:118:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |       assert(ans.size() == N);
      |              ~~~~~~~~~~~^~~~
fun.cpp:144:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |   for (i = 0; i < ans.size(); i++) assert(ans[i] != c);
      |               ~~^~~~~~~~~~~~

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