Submission #861584

#	Time	Username	Problem	Language	Result	Execution time	Memory
861584		aykhn	CONSUL (info1cup19_consul)	C++14	100 / 100	10 ms	700 KiB

consul

#include "grader.h"
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

int n;
vector<int> v;
int l;
int c = 0;

void solve(int N)
{
    srand(time(0));
    n = N;
    v.assign(n + 1, 0);
    l = 60;
    c = 0;
    int ans = -1;
    while (l && c * 2 <= n)
    {
        l--;
        if (!l) return;
        int x = rand() % n + 1;
        while (v[x]) x = rand() % n + 1;
        v[x] = 1;
        int y = kth(x);
        int cc = cnt(y);
        if (cc*3 > n) 
        {
            ans = y;
            break;
        }
        c++;
        l--;
    }
    say_answer(ans);
}

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