oj.uz

Submission #518393

# Submission time Handle Problem Language Result Execution time Memory
518393 2022-01-23T15:59:37 Z lucri CONSUL (info1cup19_consul) C++17
100 / 100
 34 ms 328 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include<stdlib.h>
#include<time.h>

/*using namespace std;

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 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];
}*/

void solve(int n)
{
    srand(time(NULL));
    int q=30;
    if(n<=50)
        q=25;
    while(--q)
    {
        int x=rand()%n+1;
        x=kth(x);
        if(cnt(x)>n/3)
        {
            say_answer(x);
            return;
        }
    }
    say_answer(-1);
}

/*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;
}*/

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 200 KB Output is correct
2 Correct 6 ms 200 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 200 KB Output is correct
2 Correct 24 ms 256 KB Output is correct
3 Correct 5 ms 200 KB Output is correct
4 Correct 7 ms 200 KB Output is correct
5 Correct 23 ms 280 KB Output is correct
6 Correct 22 ms 280 KB Output is correct
7 Correct 16 ms 200 KB Output is correct
8 Correct 23 ms 268 KB Output is correct
9 Correct 19 ms 200 KB Output is correct
10 Correct 34 ms 200 KB Output is correct
11 Correct 23 ms 200 KB Output is correct
12 Correct 23 ms 284 KB Output is correct
13 Correct 28 ms 200 KB Output is correct
14 Correct 15 ms 328 KB Output is correct