oj.uz

Submission #950154

# Submission time Handle Problem Language Result Execution time Memory
950154 2024-03-20T05:57:29 Z Pring CONSUL (info1cup19_consul) C++17
93.5 / 100
 16 ms 600 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);
    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

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.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
58.5 / 65.0

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