oj.uz

Submission #869831

# Submission time Handle Problem Language Result Execution time Memory
869831 2023-11-05T19:49:24 Z rainboy CONSUL (info1cup19_consul) C++17
100 / 100
 22 ms 580 KB 
#include "grader.h"

const int N = 1000, Q = 50, Q_ = 10;

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

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

int *xx;

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;
	}
}

int aa[N], kk[N], ii[N];

void solve(int n) {
	for (int i = 0; i < n; i++)
		ii[i] = i;
	for (int i = 0; i < n; i++) {
		int j = rand_() % (i + 1), tmp;
		tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
	}
	int n_ = min(n, Q);
	for (int h = 0; h < n_; h++)
		aa[ii[h]] = kth(ii[h] + 1);
	xx = aa, sort(ii, 0, n_);
	if (n == n_) {
		for (int h = 0; h + n / 3 < n; h++)
			if (aa[ii[h]] == aa[ii[h + n / 3]]) {
				say_answer(aa[ii[h]]);
				return;
			}
	} else {
		int n1 = 0;
		for (int h = 0; h < n_; h++)
			if (n1 == 0 || aa[ii[n1 - 1]] != aa[ii[h]])
				kk[ii[n1++] = ii[h]] = 1;
			else
				kk[ii[n1 - 1]]++;
		xx = kk, sort(ii, 0, n1);
		for (int h = n1 - 1; h >= 0 && h >= n1 - Q_; h--)
			if (cnt(aa[ii[h]]) > n / 3) {
				say_answer(aa[ii[h]]);
				return;
			}
	}
	say_answer(-1);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 420 KB Output is correct
2 Correct 17 ms 420 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 432 KB Output is correct
2 Correct 19 ms 428 KB Output is correct
3 Correct 18 ms 424 KB Output is correct
4 Correct 18 ms 428 KB Output is correct
5 Correct 19 ms 428 KB Output is correct
6 Correct 19 ms 428 KB Output is correct
7 Correct 19 ms 432 KB Output is correct
8 Correct 19 ms 432 KB Output is correct
9 Correct 19 ms 424 KB Output is correct
10 Correct 19 ms 428 KB Output is correct
11 Correct 19 ms 428 KB Output is correct
12 Correct 19 ms 428 KB Output is correct
13 Correct 19 ms 428 KB Output is correct
14 Correct 20 ms 580 KB Output is correct