oj.uz

Submission #950151

# Submission time Handle Problem Language Result Execution time Memory
950151 2024-03-20T05:55:41 Z Pring CONSUL (info1cup19_consul) C++17
19.4647 / 100
 20 ms 452 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 = 100, 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 18 ms 344 KB Output is correct

Subtask #2
3.6 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 440 KB Output is partially correct
2 Correct 5 ms 344 KB Output is correct

Subtask #3
0.864681649 / 65.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 444 KB Output is partially correct
2 Partially correct 16 ms 444 KB Output is partially correct
3 Correct 4 ms 444 KB Output is correct
4 Correct 4 ms 444 KB Output is correct
5 Partially correct 14 ms 440 KB Output is partially correct
6 Partially correct 16 ms 448 KB Output is partially correct
7 Partially correct 19 ms 452 KB Output is partially correct
8 Partially correct 20 ms 444 KB Output is partially correct
9 Partially correct 17 ms 444 KB Output is partially correct
10 Partially correct 20 ms 452 KB Output is partially correct
11 Partially correct 15 ms 448 KB Output is partially correct
12 Partially correct 15 ms 448 KB Output is partially correct
13 Partially correct 18 ms 448 KB Output is partially correct
14 Partially correct 15 ms 444 KB Output is partially correct