Submission #1234625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234625		Aisha	CONSUL (info1cup19_consul)	C++20	100 / 100	2 ms	412 KiB

consul

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

using namespace std;

mt19937 rng(143);

void solve(int n) {
    map <int, int> mp;
    map <int, int> mp2;

    int q = 0;
    int sum = 0;

    while (q < 60) {
        int r = rng() % n + 1;
        while (mp[r]) r = rng() % n + 1;
        mp[r] ++;
        int x = kth(r); q ++;
     //   cout << x << ' ' << r << ' ' << sum << endl;

        if (mp2[x]) continue;
        
        mp2[x] ++;

        int c = cnt(x);
        if (c > n / 3) {
            say_answer(x);
            return;
        } 
        sum += c;

        if (n - sum <= n / 3) break;
        q ++;
    }
   
    say_answer(-1);
}

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