Submission #1146639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146639		Dan4Life	CONSUL (info1cup19_consul)	C++20	0 / 100	3 ms	416 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 0;
	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 = 60;
	for(int i = 1; i <= n; i++) a[i]=-1;
	if(n<=50){
		if(n<=2){
			say_answer(kth(1));
			return;
		}
		for(int i = 1; i <= min(25,n); i++){
			int x = kth(i);
			if(cnt(x) > n / 3){
				say_answer(x); return;
			}
		}
		say_answer(-1); return;
	}
	vi v(n,0); iota(all(v),1);
	random_shuffle(all(v));
	for(auto i : v){
		if(!q) break;
		int x = getEle(i);
		if(getCnt(x) > n/3){
			say_answer(kth(1));
			return;
		}
	}
	say_answer(-1);
}

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