Submission #314570

#	Time	Username	Problem	Language	Result	Execution time	Memory
314570		balbit	CONSUL (info1cup19_consul)	C++14	100 / 100	62 ms	384 KiB

consul

#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 / 15
• Subtask 2: 20 / 20
• Subtask 3: 65 / 65