Submission #632155

#	Time	Username	Problem	Language	Result	Execution time	Memory
632155		boris_mihov	CONSUL (info1cup19_consul)	C++17	100 / 100	35 ms	220 KiB

consul

#include "grader.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;

std::map <int,int> map;
bool used[MAXN];

void solve(int n)
{
    if (n <= 50)
    {
        map.clear();
        for (int i = 1 ; i <= n ; ++i)
        {
            map[kth(i)]++;
        }

        for (auto [key, value] : map)
        {
            if (value > n/3)
            {
                say_answer(key);
                return;
            }
        }

        say_answer(-1);
        return;
    }

    srand(69);
    std::fill(used + 1, used + 1 + n, false);
    for (int i = 1 ; i <= std::min(n/2, 30) ; ++i)
    {
        int curr;
        do
        {
            curr = rand()%n + 1;
        } while (used[curr]);
        used[curr] = true;
        curr = kth(curr);
        if (cnt(curr) > n/3) 
        {
            say_answer(curr);
            return;
        }
    }    

    say_answer(-1);
}

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