|

General

# Author Problem Lang Verdict Time Memory Sent Judged
86179859 Practice:
JKLover
364D - 52 GNU C++17 Accepted 3993 ms 11960 KB 2020-07-07 10:36:23 2020-07-07 10:36:23

→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
{
ll out = 0, fh = 1;
char jp = getchar();
while ((jp > '9' || jp < '0') && jp != '-')
jp = getchar();
if (jp == '-')
fh = -1, jp = getchar();
while (jp >= '0' && jp <= '9')
out = out * 10 + jp - '0', jp = getchar();
return out * fh;
}
void print(ll x)
{
if (x >= 10)
print(x / 10);
putchar('0' + x % 10);
}
void write(ll x, char c)
{
if (x < 0)
putchar('-'), x = -x;
print(x);
putchar(c);
}
map<ll, int> mp;
const int N = 1e6 + 10;
int n, m;
ll a[N], ans = 1;
void solve()
{
mp.clear();
int x = (rand() << 15 | rand()) % n + 1;
for (int i = 1; i <= n; ++i)
{
ll b = __gcd(a[x], a[i]);
mp[b]++;
}
auto it = mp.end();
--it;
while (1)
{
ll d = (*it).first;
if (d <= ans)
break;
int cnt = 0;
for (auto tmp = it; tmp != mp.end() && cnt < m; ++tmp)
if ((*tmp).first % d == 0)
cnt += (*tmp).second;
if (cnt >= m)
ans = d;
if (it == mp.begin())
break;
--it;
}
}
int main()
{
n = read(), m = (n + 1) >> 1;
for (int i = 1; i <= n; ++i)
srand(time(0));
for (int k = 1; k <= 13; ++k)
solve();
write(ans, '\n');
return 0;
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?