제출 #466254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466254		flappybird	즐거운 행로 (APIO20_fun)	C++14	66 / 100	246 ms	20124 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 (e(subtree[0]).first < e(subtree[1]).first) a = 1;
		else if (e(subtree[0]).first == e(subtree[1]).first && 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[a].empty()) {
				if (subtree[b].size() < subtree[c].size()) a = c;
				else a = b;
			}
			else if (max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) == r - 1 - max({ subtree[0].size(), subtree[1].size(), subtree[2].size() })) {
				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);
	}
	return ans;
}

컴파일 시 표준 에러 (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:85: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]
   85 |     if (mx == subtree[0].size()) na = 0;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:86: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]
   86 |     if (mx == subtree[1].size()) na = 1;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:87: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]
   87 |     if (mx == subtree[2].size()) na = 2;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:88:5: warning: 'na' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     if (na == a) {
      |     ^~

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