oj.uz

Submission #814692

# Submission time Handle Problem Language Result Execution time Memory
814692 2023-08-08T09:00:59 Z fanwen CONSUL (info1cup19_consul) C++17
100 / 100
 22 ms 208 KB 
#include <bits/stdc++.h>
#include "grader.h"
 
using namespace std;
 
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
 
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }
 
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
long long Rand(long long l, long long r) { return l + jdg() % (r - l + 1); }
 
void solve(int N) {
	srand(time(nullptr));
	FOR(i, 1, min(N, 25)) {
		int x = Rand(1, N);
		x = kth(x);
		if(cnt(x) > N / 3) {
			say_answer(x);
			return;
		}
	}
	say_answer(-1);
}
 
 
#ifdef LOCAL
 
#include <bits/stdc++.h>
#include "grader.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 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()
{
	freopen("TASK.inp", "r", stdin);
	freopen("TASK.out", "w", stdout);
    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;
}
 
#endif 
// Dream it. Wish it. Do it.

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 208 KB Output is correct
2 Correct 18 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 13 ms 208 KB Output is correct
6 Correct 14 ms 208 KB Output is correct
7 Correct 14 ms 208 KB Output is correct
8 Correct 19 ms 208 KB Output is correct
9 Correct 20 ms 208 KB Output is correct
10 Correct 11 ms 208 KB Output is correct
11 Correct 22 ms 208 KB Output is correct
12 Correct 17 ms 208 KB Output is correct
13 Correct 21 ms 208 KB Output is correct
14 Correct 13 ms 208 KB Output is correct