Submission #786904

#	Time	Username	Problem	Language	Result	Execution time	Memory
786904		borisAngelov	CONSUL (info1cup19_consul)	C++17	100 / 100	31 ms	208 KiB

consul

#include "grader.h"
#include <bits/stdc++.h>

using namespace std;

void solve(int n)
{
    if (n <= 50)
    {
        map<int, int> mp;

        for (int i = 1; i <= n; ++i)
        {
            ++mp[kth(i)];
        }

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

        say_answer(-1);

        return;
    }

    srand(time(NULL));

    map<int, bool> visited;

    for (int i = 1; i <= 30; ++i)
    {
        int idx = 0;

        while (true)
        {
            idx = rand() % n + 1;

            if (visited.find(idx) == visited.end())
            {
                visited[idx] = true;
                break;
            }
        }

        int guess = kth(idx);

        if (cnt(guess) > n / 3)
        {
            say_answer(guess);
            return;
        }
    }

    say_answer(-1);
}

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