oj.uz

Submission #814691

# Submission time Handle Problem Language Result Execution time Memory
814691 2023-08-08T09:00:20 Z fanwen CONSUL (info1cup19_consul) C++17
85 / 100
 31 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, 30)) {
		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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

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

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 208 KB Output is correct
2 Correct 23 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 16 ms 208 KB Output is correct
6 Correct 25 ms 208 KB Output is correct
7 Correct 18 ms 208 KB Output is correct
8 Correct 24 ms 208 KB Output is correct
9 Correct 14 ms 208 KB Output is correct
10 Correct 16 ms 208 KB Output is correct
11 Correct 31 ms 208 KB Output is correct
12 Correct 13 ms 208 KB Output is correct
13 Correct 27 ms 208 KB Output is correct
14 Correct 14 ms 208 KB Output is correct