Submission #315025

#	Time	Username	Problem	Language	Result	Execution time	Memory
315025		Kevin_Zhang_TW	CONSUL (info1cup19_consul)	C++17	100 / 100	43 ms	504 KiB

consul

#include "grader.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;

#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }

int cnt(int x) { return 1; }
void say_answer(int v) { cerr << "Ans is " << v << '\n'; }
int kth(int i) { return 1; }

#else
#define DE(...) 0
#define deubg(...) 0
#endif
const int MAX_N = 300010;

random_device rd;
mt19937 gen(rd());
void solve(int n)
{
	uniform_int_distribution<int> dis(1, n);

	const int lim = min(n, 60);
	if (n <= 50) {
		map<int,int> CT;
		for (int i = 1;i <= n;++i)
			CT[ kth(i) ]++;
		for (auto [a, b] : CT) 
			if (b * 3 > n) {
				say_answer(a);
				return;
			}
		say_answer(-1);
		return;
	}
	vector<int> id(n);
	iota(AI(id), 1);
	shuffle(AI(id), gen);
	set<int> did;
	int use = 0;
	for (int x : id) {
		if (use + 2 > lim) break;
		++use;
		int v = kth(x);
		if (did.count(v)) continue;
		did.insert(v);
		if (cnt(v) * 3 > n) {
			say_answer(v);
			return;
		}
		++use;
	}
	say_answer(-1);
	return;
}

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