Submission #387123

#	Time	Username	Problem	Language	Result	Execution time	Memory
387123		rainboy	Fun Tour (APIO20_fun)	C++11	100 / 100	334 ms	20964 KiB

fun

#include "fun.h"
#include <cassert>
#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, 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;
		}
	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;
		}
	h_ = -1;
	for (h = 0; h < 3; h++)
		if (cnt[h] >= cnt[(h + 1) % 3] + cnt[(h + 2) % 3]) {
			h_ = h;
			break;
		}
	n_ = 0;
	if (h_ == -1) {
		i = i_;
		while (1) {
			pp[n_++] = i, cnt[h_ = type[i]]--;
			if (n == n_)
				break;
			i_ = -1;
			for (h = 0; h < 3; h++)
				if (h != h_ && 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 (h != type[i_] && cnt[h] == cnt[(h + 1) % 3] + cnt[(h + 2) % 3]) {
					if (dd[i] < dd[i_])
						pp[n_++] = i_, cnt[type[i_]]--;
					h_ = h;
					goto out;
				}
			i = i_;
		}
out:;
	}
	while (cnt[h_]) {
		int h1, h2;

		pp[n_++] = cnt[h_] == 0 ? u : qu[h_][--cnt[h_]];
		if (n - n_ == 1)
			break;
		h1 = (h_ + 1) % 3, h2 = (h_ + 2) % 3;
		pp[n_++] = !cnt[h2] || cnt[h1] && dd[qu[h1][cnt[h1] - 1]] > dd[qu[h2][cnt[h2] - 1]] ? qu[h1][--cnt[h1]] : qu[h2][--cnt[h2]];
	}
	pp[n_++] = u;
	return pp;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:119:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  119 |   pp[n_++] = !cnt[h2] || cnt[h1] && dd[qu[h1][cnt[h1] - 1]] > dd[qu[h2][cnt[h2] - 1]] ? qu[h1][--cnt[h1]] : qu[h2][--cnt[h2]];
      |                          ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fun.cpp:39:33: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   39 |  int n_, h, h_, i, i_, u, a, b, c, sz_;
      |                                 ^

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