Submission #387114

#	Time	Username	Problem	Language	Result	Execution time	Memory
387114		rainboy	Fun Tour (APIO20_fun)	C++11	31 / 100	131 ms	15488 KiB

fun

#include "fun.h"
#include <vector>

using namespace std;

const int N = 100000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int dd[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (dd[ii[j]] == dd[i_])
				j++;
			else if (dd[ii[j]] < dd[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

vector<int> createFunTour(int n, int q) {
	static int type[N], qu[3][N], cnt[3];
	vector<int> pp = vector<int>(n);
	int n_, h, i, i_, u, a, b, c, sz_;

	q = -1;
	sz_ = n + 1, u = -1;
	for (i = 0; i < n; i++) {
		int sz = attractionsBehind(0, i);

		if ((n - sz) * 2 <= n && sz_ > sz)
			sz_ = sz, u = i;
	}
	a = -1, b = -1, c = -1;
	for (i = 0; i < n; i++)
		if (i != u) {
			dd[i] = hoursRequired(u, i);
			if (dd[i] == 1) {
				if (a == -1)
					a = i;
				else if (b == -1)
					b = i;
				else
					c = i;
			}
		}
	for (i = 0; i < n; i++)
		if (i != u) {
			if (hoursRequired(a, i) == dd[i] - 1)
				type[i] = 0, qu[0][cnt[0]++] = i;
			else if (hoursRequired(b, i) == dd[i] - 1)
				type[i] = 1, qu[1][cnt[1]++] = i;
			else
				type[i] = 2, qu[2][cnt[2]++] = i;
		}
	if (cnt[0] == n / 2 || cnt[1] == n / 2)
		type[u] = 2, qu[2][cnt[2]++] = u;
	else
		type[u] = 0, qu[0][cnt[0]++] = u;
	for (h = 0; h < 3; h++)
		sort(qu[h], 0, cnt[h]);
	i_ = -1;
	for (h = 0; h < 3; h++)
		if (cnt[h]) {
			i = qu[h][cnt[h] - 1];
			if (i_ == -1 || dd[i_] < dd[i])
				i_ = i;
		}
	for (h = 0; h < 3; h++)
		if (cnt[h] == cnt[(h + 1) % 3] + cnt[(h + 2) % 3]) {
			i_ = qu[h][cnt[h] - 1];
			break;
		}
	i = i_, n_ = 0;
	while (n_ < n) {
		pp[n_++] = i;
		cnt[type[i]]--;
		if (n_ == n)
			break;
		i_ = -1;
		for (h = 0; h < 3; h++)
			if (h != type[i] && cnt[h]) {
				int i1 = qu[h][cnt[h] - 1];

				if (i_ == -1 || dd[i_] < dd[i1])
					i_ = i1;
			}
		for (h = 0; h < 3; h++)
			if (cnt[h] == cnt[(h + 1) % 3] + cnt[(h + 2) % 3]) {
				i_ = qu[h][cnt[h] - 1];
				break;
			}
		i = i_;
	}
	return pp;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:38:29: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   38 |  int n_, h, i, i_, u, a, b, c, sz_;
      |                             ^

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