oj.uz

Submission #950152

# Submission time Handle Problem Language Result Execution time Memory
950152 2024-03-20T05:56:11 Z Pring CONSUL (info1cup19_consul) C++17
93.1 / 100
 16 ms 704 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 16 ms 344 KB Output is correct

Subtask #2
19.6 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 440 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 9 ms 444 KB Output is partially correct
2 Partially correct 11 ms 700 KB Output is partially correct
3 Correct 4 ms 448 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Partially correct 9 ms 448 KB Output is partially correct
6 Partially correct 11 ms 448 KB Output is partially correct
7 Partially correct 11 ms 448 KB Output is partially correct
8 Partially correct 12 ms 448 KB Output is partially correct
9 Partially correct 11 ms 448 KB Output is partially correct
10 Partially correct 12 ms 704 KB Output is partially correct
11 Partially correct 10 ms 444 KB Output is partially correct
12 Partially correct 9 ms 452 KB Output is partially correct
13 Partially correct 12 ms 448 KB Output is partially correct
14 Partially correct 10 ms 452 KB Output is partially correct