/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 102ms 17.699 MiB
#2 Accepted 101ms 17.695 MiB
#3 Accepted 96ms 17.688 MiB
#4 Accepted 99ms 17.602 MiB
#5 Accepted 99ms 17.566 MiB
#6 Accepted 102ms 17.699 MiB
#7 Accepted 99ms 17.695 MiB
#8 Accepted 102ms 17.695 MiB
#9 Accepted 102ms 17.691 MiB
#10 Accepted 102ms 17.691 MiB
#11 Accepted 121ms 17.613 MiB
#12 Accepted 125ms 17.562 MiB
#13 Accepted 122ms 17.695 MiB
#14 Accepted 124ms 17.707 MiB
#15 Accepted 130ms 17.773 MiB
#16 Accepted 127ms 17.875 MiB
#17 Accepted 189ms 18.461 MiB
#18 Accepted 113ms 17.703 MiB
#19 Accepted 139ms 17.902 MiB
#20 Accepted 129ms 17.918 MiB
#21 Accepted 127ms 17.922 MiB
#22 Accepted 125ms 17.977 MiB
#23 Accepted 121ms 17.758 MiB
#24 Accepted 133ms 17.914 MiB
#25 Accepted 135ms 17.73 MiB
#26 Accepted 136ms 17.887 MiB
#27 Accepted 128ms 17.859 MiB
#28 Accepted 119ms 17.898 MiB
#29 Accepted 124ms 17.98 MiB
#30 Accepted 129ms 18.461 MiB
#31 Accepted 126ms 18.371 MiB
#32 Accepted 110ms 17.77 MiB
#33 Accepted 108ms 18.402 MiB
#34 Accepted 110ms 17.762 MiB
#35 Accepted 156ms 18.473 MiB

Code

/*For today, you happen to be the defeated. But what will you become tomorrow?*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define dbg if(debugg)
#define F first 
#define S second 
#define int long long
bool debugg = false;

template <typename T>
using order_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  

const int N = 100005;
vector<int>divisors[N];
void sieve()
{
    for(int i = 1; i < N; i ++){
        for(int j = i; j < N; j += i){
            divisors[j].push_back(i);
        }
    }
}
int cnt[N], tot[N];
void solve()
{
    
    int n;
    cin >> n;
    vector<int>v(n);
    int gd = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(tot, 0, sizeof(tot));
    for(int i = 0; i < n; i ++){
        cin >> v[i];
        gd = __gcd(gd, v[i]);
        cnt[v[i]] += 1;
    }

    for(int i = 1; i < N; i ++){
        for(int j = i; j < N; j += i){
            tot[i] += cnt[j];
        }
    }
    int ans = 2 * gd;
	assert(n > 0);
    for(int itr = 0; itr < 10; itr ++){
        int x = v[rng() % n], y = v[rng() % n];
        for(int i : divisors[x]){
            for(int j : divisors[y]){
                
                if(i == j) continue;
                int lm = (1ll * i * j) / gcd(i, j);
                if(lm >= N) lm = 0;
				assert(lm < N);
                if(tot[i] + tot[j] - tot[lm] != n) continue;
                int p = tot[i], q = tot[j];
                if(max(p, q) >= ((n + 1) / 2)){
                    if(min(p, q) >= (n / 2)){
                        ans = max(ans, i + j);
                    }
                }
                
            }
        }
    }

    cout << ans << '\n';
}



int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t  = 1;
    cin>>t;

    sieve();

    while(t--){

        solve();

    }

    return 0;

}

Information

Submit By
Type
Submission
Problem
P1077 Even Odd GCD (Hard Version)
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-17 05:59:52
Judged At
2024-11-11 03:09:24
Judged By
Score
100
Total Time
189ms
Peak Memory
18.473 MiB