Submission #1208537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208537		k1r1t0	Fun Tour (APIO20_fun)	C++20	47 / 100	77 ms	15808 KiB

fun

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int hoursRequired(int X, int Y);

int attractionsBehind(int X, int Y);

namespace k1r1t0 {
	const int N = 110000;

	bool used[N];
	int n, d[N], ds[N][2];
	vector<int> v[3];
	
	vector<int> createFunTour(int N, int Q) {
		n = N;
		array<int, 2> mn = {n, 0};
		for (int i = 1; i < n; i++) {
			int sz = attractionsBehind(0, i);
			if (2 * sz >= n) mn = min(mn, {sz, i});
		}
		int r = mn[1];
		for (int i = 0; i < n; i++)
			d[i] = hoursRequired(r, i);
		vector<int> sub;
		for (int i = 0; i < n; i++)
			if (d[i] == 1)
				sub.push_back(i);
		int cnt = (int) sub.size();
		for (int i = 0; i < cnt - 1; i++)
			for (int j = 0; j < n; j++)
				ds[j][i] = hoursRequired(sub[i], j);
		for (int i = 0; i < n; i++) {
			if (i == r) continue;
			int t = cnt - 1;
			for (int j = 0; j < cnt - 1; j++)
				if (ds[i][j] + 1 == d[i])
					t = j;
			v[t].push_back(i);
		}
		if (cnt == 1)
			return {0, 1};
		int sm = 0;
		for (int i = 1; i <= 2; i++)
			if (v[sm].size() > v[i].size())
				sm = i;
		v[sm].push_back(r);
		for (int k = 0; k < 3; k++)
			sort(begin(v[k]), end(v[k]), [&](int i, int j) {return d[i] < d[j];});
		random_shuffle(v, v + 3);
		vector<int> ans;
		int t = 0;
		for (int i = 1; i <= 2; i++)
			if (!v[i].empty() && (v[t].empty() || d[v[i].back()] > d[v[t].back()]))
				t = i;
		srand(time(NULL));
		for (int i = 0; i < n; i++) {
			int j = (t + 1) % 3;
			int k = (t + 2) % 3;
			int a = v[t].size();
			int b = v[j].size();
			int c = v[k].size();
			if (b > c) {
				swap(j, k);
				swap(b, c);
			}
			if (a - 1 + b < c && b != 0) {
				if (d[v[j].back()] > d[v[c].back()] && (v[i].size() == 1 || d[v[j].back()] > d[end(v[i])[-2]])) {
					vector<int> na = v[j];
					v[j].clear();
					na.insert(na.end(), v[t].begin(), v[t].end());
					v[t] = na;
					ans.push_back(v[t].back());
					v[t].pop_back();
					sort(begin(v[t]), end(v[t]), [&](int i, int j) {return d[i] < d[j];});
				} else {
					vector<int> na = v[j];
					v[j].clear();
					na.insert(na.end(), v[t].begin(), v[t].end());
					v[t] = na;
					ans.push_back(v[t].back());
					v[t].pop_back();
					sort(begin(v[t]), end(v[t]), [&](int i, int j) {return d[i] < d[j];});
					t = k;
				}
			} else {
				ans.push_back(v[t].back());
				v[t].pop_back();
				if (v[j].empty() && v[k].empty())
					continue;
				if (v[j].empty()) t = k;
				else if (v[k].empty()) t = j;
				else {
					if (d[v[j].back()] > d[v[k].back()]) t = j;
					else t = k;
				}
			}
		}
		return ans;
	}
};

vector<int> createFunTour(int N, int Q) {
	return k1r1t0::createFunTour(N, Q);
}

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