Submission #1146648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146648		Dan4Life	CONSUL (info1cup19_consul)	C++20	100 / 100	7 ms	428 KiB

consul

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)s.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
int a[10000];
map<int,int> M;
int q;

int getEle(int i){
	if(!q) return -1;
	if(a[i]!=-1) return a[i];
	q--; return a[i]=kth(i);
}

int getCnt(int a){
	if(!q) return 0;
	if(M.find(a)!=end(M)) return M[a];
	q--; return M[a]=cnt(a);
}

void solve(int n){
	srand(time(0)); M.clear(); q = 50;
	for(int i = 1; i <= n; i++) a[i]=-1;
	vi v(n,0); iota(all(v),1);
	random_shuffle(all(v));
	for(auto i : v){
		int x = getEle(i);
		if(x==-1 or !q) break;
		if(getCnt(x) > n/3){
			say_answer(x); return;
		}
	}
	say_answer(-1);
}

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