Submission #466216

#	Time	Username	Problem	Language	Result	Execution time	Memory
466216		flappybird	Fun Tour (APIO20_fun)	C++17	10 / 100	1 ms	332 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 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(e(subtree[a]).second);
			subtree[a].pop_back();
			ll b, c;
			b = a + 1;
			c = a + 2;
			b %= 3;
			c %= 3;
			if (subtree[b].size() < subtree[c].size()) a = c;
			else a = b;
			r--;
		}
		ans.push_back(c);
	}
	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++) {
      |              ~~^~~~~~~~~~~~

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