/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 328.0 KiB
#2 Wrong Answer 2ms 552.0 KiB
#3 Wrong Answer 3ms 328.0 KiB

Code

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
#define sz(x) (ll)(x).size()
#define rd ({ll x; cin >> x; x; })
#define dbg(x) cerr << "[" #x "]  " << (x) << "\n\n"
// #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
// #define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
// #define cerr if(0)cerr
#define xx first
#define yy second
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
/*_________________________________________________________________________________________________________________________*/

void Solve()
{
    ll n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr.begin(), arr.end());
    ll ans = 2;
    vector<ll> q;
    for (int i = 1; i <= arr[0]; i++)
        if (arr[0] % i == 0)
            q.push_back(i);
    multiset<ll> mst;
    for (auto& it : arr)
        mst.insert(it);
    for (auto& Q : q) {
        multiset<ll> reserve;
        multiset<ll> tmp = mst;
        for (auto& it : mst)
            if (it % Q == 0)
                reserve.insert(it);
        for (auto& it : reserve)
            tmp.erase(tmp.find(it));
        if (sz(reserve) < n / 2)
            continue;
        ll gc = 0;
        for (auto& it : tmp)
            gc = __gcd(gc, it);
        ll shortage = sz(reserve) - n / 2;
        vector<ll> toCheck;
        for (int i = 1; i <= gc; i++)
            if (gc % i == 0)
                toCheck.push_back(i);
        sort(toCheck.rbegin(), toCheck.rend());
        for (auto& it : toCheck) {
            ll cnt = 0;
            for (auto& jt : reserve)
                if (jt % it == 0)
                    cnt += 1;
            if (cnt >= shortage) {
                ans = max(ans, Q + it);
                break;
            }
        }
        if (n % 2 == 1 && sz(reserve) >= n / 2 + 1)
        {
            ll shortage = sz(reserve) - n / 2 - 1;
            vector<ll> toCheck;
            for (int i = 1; i <= gc; i++)
                if (gc % i == 0)
                    toCheck.push_back(i);
            sort(toCheck.rbegin(), toCheck.rend());
            for (auto& it : toCheck) {
                ll cnt = 0;
                for (auto& jt : reserve)
                    if (jt % it == 0)
                        cnt += 1;
                if (cnt >= shortage) {
                    ans = max(ans, Q + it);
                    break;
                }
            }
        }
    }
    cout << ans << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": "; // cout << "Case " << i << ": ";
        Solve();
    }
    return 0;
}
// Coded by Tahsin Arafat (@TahsinArafat)

Information

Submit By
Type
Submission
Problem
P1076 Even Odd GCD (Easy Version)
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 17:28:04
Judged At
2024-11-11 03:11:40
Judged By
Score
1
Total Time
3ms
Peak Memory
552.0 KiB