oj.uz

Submission #950148

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

Subtask #2
3.6 / 20.0

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

Subtask #3
0.864681649 / 65.0

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