Submission #1220697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220697		rainboy	Rotating Lines (APIO25_rotate)	C++20	100 / 100	43 ms	2928 KiB

rotate

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

using namespace std;

typedef vector<int> vi;

const int N = 100000, X = 50000;

unsigned int Z = 12345;

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

int xx[N], ii[N], jj[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 (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[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;
	}
}

void energy(int n, vi xx_) {
	for (int i = 0; i < n; i++)
		xx[i] = xx_[i];
	for (int i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	int k = 0;
	while (k < n && xx[ii[k]] < X / 2)
		k++;
	if (k > n / 2) {
		for (int i = 0; i < n; i++)
			xx[i] = (xx[i] + X / 2) % X;
		for (int i = 0; i < n; i++)
			jj[i] = ii[(i + k) % n];
		for (int i = 0; i < n; i++)
			ii[i] = jj[i];
	}
	for (int g = 0; g < n / 2; g++) {
		int i = ii[g];
		if (xx[i] >= X / 2)
			rotate({ i }, X - (xx[i] - X / 2 + 1)), xx[i] = X / 2 - 1;
	}
	for (int h = n / 2; h < n; h++)
		xx[ii[h]] -= X / 2;
	int g = 0, h = n / 2;
	while (g < n / 2 || h < n)
		if (h == n || g < n / 2 && xx[ii[g]] < xx[ii[h]]) {
			if (g < h - n / 2)
				rotate({ ii[g] }, X - (xx[ii[g]] - xx[ii[g + n / 2]]));
			g++;
		} else {
			if (h - n / 2 < g)
				rotate({ ii[h] }, X - (xx[ii[h]] - xx[ii[h - n / 2]]));
			h++;
		}
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 26 / 26