Submission #291694

#	Time	Username	Problem	Language	Result	Execution time	Memory
291694		nvmdava	Fun Tour (APIO20_fun)	C++17	100 / 100	374 ms	20464 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d[N];
vector<int> id;
vector<pair<int, int> > ch[4];
vector<int> ans;


std::vector<int> createFunTour(int N, int Q) {
	int r = 0, cn = 0, mxw = N + 5;
	for(int i = 1; i < N; ++i){
		int w = attractionsBehind(r, i);
		if(w >= (N + 1) / 2){
			if(w < mxw){
				cn = i;
				mxw = w;
			}
		}
	}

	r = cn;

	for(int i = 0; i < N; ++i){
		if(i == r) continue;
		d[i] = hoursRequired(i, r);
		if(d[i] == 1)
			id.push_back(i);
	}
	for(int i = 0; i < N; ++i){
		if(i == r) continue;
		bool ok = 0;
		for(int j = 1; j < id.size(); ++j){
			if(d[i] - 1 == hoursRequired(id[j], i)){
				ch[j].push_back({d[i], i});
				ok = 1;
				break;
			}
		}
		if(!ok){
			ch[0].push_back({d[i], i});
		}
	}

	int szz = 0;
	if(ch[1].size() < ch[szz].size()) szz = 1;
	if(ch[2].size() < ch[szz].size()) szz = 2;
	ch[szz].push_back({d[r], r});

	for(int i = 0; i < id.size(); ++i)
		sort(ch[i].begin(), ch[i].end());

	int la = -1;

	int cnt = N;

	while(cnt){

		if(max(ch[0].size(), max(ch[1].size(), ch[2].size())) * 2 == cnt){
			break;
		}

		int now = -1;
		for(int i = 0; i < 3; ++i){
			if(la == i) continue;
			if(ch[i].empty()) continue;
			if(now == -1 || ch[now].back().ff < ch[i].back().ff)
				now = i;
		}
		la = now;
		ans.push_back(ch[now].back().ss);
		ch[now].pop_back();
		cnt--;
	}

	if(ch[0].size() < ch[1].size()){
		swap(ch[0], ch[1]);
		if(la == 0) la = 1;
		else if(la == 1) la = 0;
	}

	if(ch[0].size() < ch[2].size()){
		swap(ch[0], ch[2]);
		if(la == 0) la = 2;
		else if(la == 2) la = 0;
	}

	if(ch[1].size() < ch[2].size()){
		swap(ch[1], ch[2]);
		if(la == 1) la = 2;
		else if(la == 2) la = 1;
	}

	if(!ch[2].empty()){
		if(ch[2].back().ff > ch[1].back().ff){
			swap(ch[1], ch[2]);
			if(la == 1) la = 2;
			else if(la == 2) la = 1;
		}
	}

	if(!ch[1].empty() && (la == 0 || (la == 2 && ch[1].back().ff > ch[0].back().ff))){
		la = 1;
		ans.push_back(ch[1].back().ss);
		ch[1].pop_back();
		cnt--;
	}
	while(cnt){
		if(!ch[0].empty()){
			ans.push_back(ch[0].back().ss);
			ch[0].pop_back();
			cnt--;
		}
		if(ch[1].empty() && ch[2].empty()){
			continue;
		}
		if(ch[1].empty()){
			ans.push_back(ch[2].back().ss);
			ch[2].pop_back();
			cnt--;
			continue;
		}
		if(ch[2].empty()){
			ans.push_back(ch[1].back().ss);
			ch[1].pop_back();
			cnt--;
			continue;
		}
		if(ch[1].back().ff < ch[2].back().ff){
			swap(ch[1], ch[2]);
		}
		ans.push_back(ch[1].back().ss);
		ch[1].pop_back();
		cnt--;
	}

	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int j = 1; j < id.size(); ++j){
      |                  ~~^~~~~~~~~~~
fun.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < id.size(); ++i)
      |                 ~~^~~~~~~~~~~
fun.cpp:64:61: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   64 |   if(max(ch[0].size(), max(ch[1].size(), ch[2].size())) * 2 == cnt){
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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