Submission #690528

#	Time	Username	Problem	Language	Result	Execution time	Memory
690528		alexdd	CONSUL (info1cup19_consul)	C++17	100 / 100	26 ms	348 KiB

consul

#include<bits/stdc++.h>
#include "grader.h"
using namespace std;

unordered_map<int,int> fr1;
unordered_map<int,bool> bl1;
unordered_map<int,int> fr2;
unordered_map<int,bool> bl2;
int maxq;
int cntq;
int actual_kth(int k)
{
    if(bl1[k]==0)
    {
        fr1[k]=kth(k);
        bl1[k]=1;
        cntq++;
    }
    return fr1[k];
}
int actual_cnt(int x)
{
    if(bl2[x]==0)
    {
        fr2[x]=cnt(x);
        bl2[x]=1;
        cntq++;
    }
    return fr2[x];
}

void solve(int n)
{
    cntq=0;
    fr1.clear();
    bl1.clear();
    fr2.clear();
    bl2.clear();
    maxq=min(60,n);

    mt19937 rnd(82396293);

    while(cntq+2<=maxq)
    {
        int x = 1 + (rnd())%n;
        if(bl1[x]==0)
        {
            int care = actual_kth(x);
            if(actual_cnt(care) > n/3)
            {
                say_answer(care);
                return;
            }
        }
    }
    say_answer(-1);
    return;
}

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