Submission #1170692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170692		browntoad	CONSUL (info1cup19_consul)	C++20	100 / 100	11 ms	408 KiB

consul

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

void solve(int n)
{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    vector<bool> occ(n+1);

    if (n <= 50){
        map<int, int> mp;
        REP1(i, n){
            mp[kth(i)]++;
        }
        for (auto pp:mp){
            if (pp.s > n/3){
                say_answer(pp.f);
                return;
            }
        }
        say_answer(-1);
        return;
    }

    int rem = n;
    REP(i, 30){
        if (rem == 0) break;
        int pp = rng()%n+1;
        while(occ[pp]){
            pp = rng()%n+1;
        }
        
        occ[pp] = 1;
        rem--;
        int nipple = kth(pp);
        if (cnt(nipple) > n/3) {
            say_answer(nipple);
            return;
        }
    }
    say_answer(-1);

    /// insert your code
    /// for example
    /*if(cnt(kth(1)) > n / 3) say_answer(kth(1));
        else say_answer(-1);
    */
}

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