Submission #466303

#	Time	Username	Problem	Language	Result	Execution time	Memory
466303		flappybird	Fun Tour (APIO20_fun)	C++14	66 / 100	271 ms	21068 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;
	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;
		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]);
		a = 2;
		while (r != 1) {
			ans.push_back(subtree[a][subtree[a].size() - 1].second);
			subtree[a].pop_back();
			ll b, c;
			b = a + 1;
			c = a + 2;
			b %= 3;
			c %= 3;
			if (chk||max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= (r-1)/2) {
              chk=1;
				ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() });
				ll na;
				if (mx == subtree[0].size()) na = 0;
				if (mx == subtree[1].size()) na = 1;
				if (mx == subtree[2].size()) na = 2;
				if (na == a) {
					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 a = na;
			}
			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--;
		}
		ans.push_back(c);
	}
  assert(ans.size()==N);
	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:78:78: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'll' {aka 'int'} [-Wsign-compare]
   78 |    if (chk||max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= (r-1)/2) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
fun.cpp:82:12: 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]
   82 |     if (mx == subtree[0].size()) na = 0;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:83:12: 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]
   83 |     if (mx == subtree[1].size()) na = 1;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:84:12: 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]
   84 |     if (mx == subtree[2].size()) na = 2;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from fun.cpp:3:
fun.cpp:101:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |   assert(ans.size()==N);
      |          ~~~~~~~~~~^~~
fun.cpp:85:5: warning: 'na' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     if (na == a) {
      |     ^~

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