oj.uz

Submission #314570

# Submission time Handle Problem Language Result Execution time Memory
314570 2020-10-20T10:17:30 Z balbit CONSUL (info1cup19_consul) C++14
100 / 100
 62 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef BALBIT
#include "grader.h"
#endif

#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x.size())

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif

#ifdef BALBIT
int kth(int x){bug("k", x); int y; cin>>y; return y;}
int cnt(int x){bug("c", x); int y; cin>>y; return y;}
void say_answer(int x) {bug(x); }
#endif // BALBIT

mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());

void solve(int n) {

    map<int, int> mp;
    vector<int> p(n);
    for (int i = 0; i<n; ++i) p[i] = i;
    shuffle(ALL(p), rng);
    int qleft = 50;
    for (int i = 0; i<n && SZ(mp)+1 < qleft-1; ++i) {
        mp[kth(p[i]+1)]++; --qleft;
    }

    for (pii p : mp) {
        int cc = cnt(p.f);
        if (cc * 3 > n) {
            say_answer(p.f);
            return;
        }
    }
    say_answer(-1);
}


#ifdef BALBIT
signed main(){
    bug(1,2);
    solve(3);
}

#endif // BALBIT

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 256 KB Output is correct
2 Correct 44 ms 256 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 384 KB Output is correct
2 Correct 62 ms 380 KB Output is correct
3 Correct 58 ms 384 KB Output is correct
4 Correct 42 ms 376 KB Output is correct
5 Correct 56 ms 384 KB Output is correct
6 Correct 40 ms 256 KB Output is correct
7 Correct 35 ms 384 KB Output is correct
8 Correct 27 ms 384 KB Output is correct
9 Correct 40 ms 256 KB Output is correct
10 Correct 52 ms 384 KB Output is correct
11 Correct 39 ms 256 KB Output is correct
12 Correct 40 ms 384 KB Output is correct
13 Correct 50 ms 384 KB Output is correct
14 Correct 31 ms 384 KB Output is correct