Submission #466523

#	Time	Username	Problem	Language	Result	Execution time	Memory
466523		zigui	Fun Tour (APIO20_fun)	C++17	66 / 100	263 ms	42496 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;
		while (r != 1) {
            assert(subtree[a].size() >= 1);
			ll loc = subtree[a][subtree[a].size() - 1].second;
			//assert(asdf[loc] == a);
			ans.push_back(loc);
			subtree[a].pop_back();
			ll b, c;
			b = a + 1;
			c = a + 2;
			b %= 3;
			c %= 3;
			if (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--;
		}
		for (i = 0; i < ans.size(); i++) assert(ans[i] != c);
		ans.push_back(c);
	}
	assert(!(subtree[0].size() + subtree[1].size() + subtree[2].size()));
	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:92:73: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'll' {aka 'int'} [-Wsign-compare]
   92 |    if (max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) == (r - 1) / 2) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fun.cpp:96: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]
   96 |     if (mx == subtree[0].size()) na = 0;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:97: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]
   97 |     if (mx == subtree[1].size()) na = 1;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:98: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]
   98 |     if (mx == subtree[2].size()) na = 2;
      |         ~~~^~~~~~~~~~~~~~~~~~~~
fun.cpp:113:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (i = 0; i < ans.size(); i++) assert(ans[i] != c);
      |               ~~^~~~~~~~~~~~
fun.cpp:63:6: warning: variable 'chk' set but not used [-Wunused-but-set-variable]
   63 |   ll chk = 0;
      |      ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from fun.cpp:3:
fun.cpp:117:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |  assert(ans.size() == N);
      |         ~~~~~~~~~~~^~~~
fun.cpp:99:5: warning: 'na' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |     if (na == a) {
      |     ^~

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