oj.uz

Submission #246293

# Submission time Handle Problem Language Result Execution time Memory
246293 2020-07-08T15:04:37 Z lovemathboy CONSUL (info1cup19_consul) C++14
85 / 100
 73 ms 384 KB 
#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-1, 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 < 10; i++) {
		if (cnt(totals[i].second) > n/3) {
			say_answer(totals[i].second);
			return;
		}
	}
	say_answer(-1);
	return;
}

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 256 KB Output isn't correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 256 KB Output is correct
2 Correct 61 ms 256 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 384 KB Output is correct
2 Correct 71 ms 256 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 50 ms 384 KB Output is correct
5 Correct 66 ms 384 KB Output is correct
6 Correct 65 ms 256 KB Output is correct
7 Correct 56 ms 384 KB Output is correct
8 Correct 56 ms 256 KB Output is correct
9 Correct 66 ms 384 KB Output is correct
10 Correct 53 ms 256 KB Output is correct
11 Correct 53 ms 256 KB Output is correct
12 Correct 45 ms 256 KB Output is correct
13 Correct 53 ms 256 KB Output is correct
14 Correct 70 ms 256 KB Output is correct