Submission #950156

#	Time	Username	Problem	Language	Result	Execution time	Memory
950156		Pring	CONSUL (info1cup19_consul)	C++17	93.50 / 100	20 ms	704 KiB

consul

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

#define fs first
#define sc second
#define mp make_pai
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
mt19937 rnd(39393939);

void solve(int n) {
    if (n <= 50) {
        map<int, int> M;
        FOR(i, 1, n + 1) {
            int x = kth(i);
            if (++M[x] > n / 3) {
                say_answer(x);
                return;
            }
        }
        say_answer(-1);
        return;
    }
    vector<int> v;
    set<int> S;
    FOR(i, 1, n + 1) v.push_back(i);
    shuffle(v.begin(), v.end(), rnd);
    while (v.size() > 40) v.pop_back();
    int bound = 60, p = 0;
    while (bound > 0) {
        int id = v[p];
        int x = kth(id);
        bound--;
        if (S.insert(x).sc) {
            int y = cnt(x);
            bound--;
            if (y > n / 3) {
                say_answer(x);
                return;
            }
        }
        if (++p == v.size()) break;
    }
    say_answer(-1);
    return;
}

Compilation message (stderr)

consul.cpp: In function 'void solve(int)':
consul.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (++p == v.size()) break;
      |             ~~~~^~~~~~~~~~~

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