Submission #401017

#	Time	Username	Problem	Language	Result	Execution time	Memory
401017		dolphingarlic	CONSUL (info1cup19_consul)	C++14	100 / 100	19 ms	296 KiB

consul

#include "grader.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

void solve(int n) {
    srand(69420);
    set<int> found;
    int unknown = n;
    vector<int> rem(n);
    iota(rem.begin(), rem.end(), 1);
    random_shuffle(rem.begin(), rem.end());

    int queries = 60;
    while (unknown > n / 3 && queries > 1) {
        int curr = rem.back();
        rem.pop_back();
        int v = kth(curr);
        queries--;
        if (found.count(v)) continue;
        found.insert(v);
        int c = cnt(v);
        queries--;
        if (c > n / 3) {
            say_answer(v);
            return;
        }
        unknown -= c;
    }
    say_answer(-1);
}

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