oj.uz

Submission #814685

# Submission time Handle Problem Language Result Execution time Memory
814685 2023-08-08T08:59:09 Z fanwen CONSUL (info1cup19_consul) C++17
4.96076 / 100
 34 ms 296 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, 50) {
		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 11 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 208 KB Output is partially correct
2 Correct 5 ms 208 KB Output is correct

Subtask #3
0.9607573885 / 65.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 208 KB Output is partially correct
2 Partially correct 28 ms 208 KB Output is partially correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 5 ms 292 KB Output is correct
5 Partially correct 28 ms 208 KB Output is partially correct
6 Partially correct 23 ms 296 KB Output is partially correct
7 Partially correct 21 ms 208 KB Output is partially correct
8 Partially correct 29 ms 208 KB Output is partially correct
9 Partially correct 33 ms 208 KB Output is partially correct
10 Partially correct 33 ms 292 KB Output is partially correct
11 Partially correct 34 ms 208 KB Output is partially correct
12 Partially correct 30 ms 208 KB Output is partially correct
13 Partially correct 27 ms 208 KB Output is partially correct
14 Partially correct 21 ms 208 KB Output is partially correct