Submission #409645

#	Time	Username	Problem	Language	Result	Execution time	Memory
409645		Atill83	CONSUL (info1cup19_consul)	C++14	100 / 100	37 ms	460 KiB

consul

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int num[60005];

unordered_map<int, int> mp;

void solve(int n)
{
    memset(num, -1, sizeof(num));
    mt19937 rng(time(NULL));
    int q = (n <= 50 ? 50 : 60);
    while(q >= 2){
        int idx = rng() % n + 1;
        if(num[idx] == -1){
            q--;
            num[idx] = kth(idx);
        }
        auto u = mp.find(num[idx]);
        int cn;
        if(u == mp.end()){
            cn = cnt(num[idx]);
            q--; 
        }else{
            cn = (*u).second;
        }
        if(cn > n / 3){
            say_answer(num[idx]);
            return;
        }
    }
    
    say_answer(-1);
}

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