| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1315344 | muhammad-ahmad | CONSUL (info1cup19_consul) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #include "grader.h"
// #include "A.cpp"
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 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];
}
void solve(int N){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int l = 1, r = N;
int ans = -1;
for (int q = 1; q <= 25; q++){
int x = uniform_int_distribution<int>(l,r)(rng);
int val = kth(x);
int C = cnt(val);
if (C > N / 3) ans = val;
}
say_answer(ans);
}
int main()
{
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;
}