Submission #341980

#	Time	Username	Problem	Language	Result	Execution time	Memory
341980		cheissmart	CONSUL (info1cup19_consul)	C++14	100 / 100	29 ms	364 KiB

consul

#include "grader.h"
#ifdef CHEISSMART
#include "grader.cpp"
#endif
#include <bits/stdc++.h>

using namespace std;

void solve(int n) {
	set<int> asked;
	int qry = 0;
	auto is = [&] (int i) {
		int x = kth(i);
		qry++;
		if(asked.count(x)) return -1;
		asked.insert(x);
		qry++;
		if(cnt(x) * 3 > n) return x;
		else return -1;
	};
	mt19937 rng(time(0));
	while(qry + 2 <= 50) {
		int pos = rng() % n + 1;
		int r = is(pos);
		if(r != -1) {
			say_answer(r);
			return;
		}
	}
 	say_answer(-1);
}

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