oj.uz

Submission #950153

# Submission time Handle Problem Language Result Execution time Memory
950153 2024-03-20T05:56:36 Z Pring CONSUL (info1cup19_consul) C++17
93.1 / 100
 15 ms 696 KB 
#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(time(nullptr));

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);
    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 == n) break;
    }
    say_answer(-1);
    return;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 344 KB Output is correct

Subtask #2
19.6 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 344 KB Output is partially correct
2 Correct 3 ms 344 KB Output is correct

Subtask #3
58.5 / 65.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 448 KB Output is partially correct
2 Partially correct 10 ms 452 KB Output is partially correct
3 Correct 4 ms 444 KB Output is correct
4 Correct 4 ms 448 KB Output is correct
5 Partially correct 10 ms 452 KB Output is partially correct
6 Partially correct 10 ms 344 KB Output is partially correct
7 Partially correct 11 ms 600 KB Output is partially correct
8 Partially correct 13 ms 448 KB Output is partially correct
9 Partially correct 11 ms 444 KB Output is partially correct
10 Partially correct 11 ms 696 KB Output is partially correct
11 Partially correct 11 ms 444 KB Output is partially correct
12 Partially correct 9 ms 444 KB Output is partially correct
13 Partially correct 12 ms 452 KB Output is partially correct
14 Partially correct 10 ms 452 KB Output is partially correct