Submission #515571

#	Time	Username	Problem	Language	Result	Execution time	Memory
515571		Theo830	CONSUL (info1cup19_consul)	C++17	0 / 100	14 ms	280 KiB

consul

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "grader.h"
/*
static const int MIN_VALUE = 0, MAX_VALUE = (1e9) - 1;

static map<int,int> mp;
static int Q, N, a[5005];
static bool issol, answer;

void solve(int N);

void say_answer(int k)
{
    if(answer)
    {
        cout << "Multiple answers provided for the same testcase!\n";
        exit(0);
    }
    answer = 1;

    if(k == -1)
    {
        if(issol)
        {
            cout << "Wrong answer\n";
            exit(0);
        }
        else cout << "Correct! Number of queries: " << Q << '\n';
    }
    else
    {
        if(!issol || mp[k] <= N/3)
        {
            cout << "Wrong answer\n";
            exit(0);
        }
        else cout << "Correct! Number of queries: " << Q << '\n';
    }
}

int cnt(int k)
{
    ++Q;
    if(!(k>=MIN_VALUE && k<=MAX_VALUE))
    {
        cout << "Wrong query format\n";
        exit(0);
    }
    return mp[k];
}

int kth(int k)
{
    ++Q;
    if(!(k>=1 && k<=N))
    {
        cout << "Wrong query format\n";
        exit(0);
    }
    return a[k];
}

int main()
{
    int tests, i;
    cin >> tests;

    while(tests--)
    {
        cin >> N; mp.clear();
        Q = 0; issol = 0; answer = 0;

        for(i=1; i<=N; ++i) cin >> a[i], ++mp[a[i]];
        for(i=1; i<=N; ++i) issol |= (mp[a[i]] > N/3);
        solve(N);
    }

    return 0;
}
*/
void solve(int n){
    srand(time(0));
    map<ll,bool>ekama;
    while(1){
        ll pos = rand() % n;
        pos++;
        ll val = kth(pos);
        if(!ekama[val]){
            ekama[val] = true;
            if(cnt(val) > n / 3){
                say_answer(val);
                return;
            }
        }
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 65