oj.uz

Submission #814688

# Submission time Handle Problem Language Result Execution time Memory
814688 2023-08-08T08:59:45 Z fanwen CONSUL (info1cup19_consul) C++17
85 / 100
 28 ms 256 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, 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 5 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 8 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct

Subtask #3
65.0 / 65.0

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