Submission #246298

#	Time	Username	Problem	Language	Result	Execution time	Memory
246298		lovemathboy	CONSUL (info1cup19_consul)	C++14	85 / 100	74 ms	416 KiB

consul

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

void solve(int n)
{
	vector<int> r;
	for (int i = 1; i <= n; i++) r.push_back(i);
	random_shuffle(r.begin(), r.end());
	map<int, int> m;
	set<int> s;
	for (int i = 0; i < min(n, 50); i++) {
		int val = kth(r[i]);
		m[val]++;
		s.insert(val);
	}
	vector<pair<int, int> > totals;
	for (int i: s) {
		totals.emplace_back(-m[i], i);
	}
	sort(totals.begin(), totals.end());
	for (int i = 0; i < min((int)totals.size(), 10); i++) {
		if (-totals[i].first > n/3) {
			say_answer(totals[i].second);
			return;
		}
		if (cnt(totals[i].second) > n/3) {
			say_answer(totals[i].second);
			return;
		}
	}
	say_answer(-1);
	return;
}

• Subtask 1: 0 / 15
• Subtask 2: 20 / 20
• Subtask 3: 65 / 65