Submission #814688

#	Time	Username	Problem	Language	Result	Execution time	Memory
814688		fanwen	CONSUL (info1cup19_consul)	C++17	85 / 100	28 ms	256 KiB

consul

#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 / 15
• Subtask 2: 20 / 20
• Subtask 3: 65 / 65