oj.uz

Submission #515574

# Submission time Handle Problem Language Result Execution time Memory
515574 2022-01-19T09:03:11 Z Theo830 CONSUL (info1cup19_consul) C++17
100 / 100
 32 ms 280 KB 
#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;
    ll q = 30;
    if(n <= 50){
        q = 25;
    }
    while(q--){
        ll pos = rand() % n;
        pos++;
        ll val = kth(pos);
        if(!ekama[val]){
            ekama[val] = true;
            if(cnt(val) > n / 3){
                say_answer(val);
                return;
            }
        }
    }
    say_answer(-1);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 200 KB Output is correct
2 Correct 3 ms 260 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 200 KB Output is correct
2 Correct 13 ms 200 KB Output is correct
3 Correct 5 ms 264 KB Output is correct
4 Correct 3 ms 268 KB Output is correct
5 Correct 7 ms 268 KB Output is correct
6 Correct 19 ms 200 KB Output is correct
7 Correct 18 ms 280 KB Output is correct
8 Correct 32 ms 264 KB Output is correct
9 Correct 19 ms 200 KB Output is correct
10 Correct 20 ms 200 KB Output is correct
11 Correct 20 ms 200 KB Output is correct
12 Correct 18 ms 200 KB Output is correct
13 Correct 21 ms 200 KB Output is correct
14 Correct 21 ms 264 KB Output is correct