/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Wrong Answer 2ms 320.0 KiB
#3 Accepted 2ms 320.0 KiB
#4 Wrong Answer 2ms 320.0 KiB

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 int long long int 
#define dbg if(debugg)
#define F first 
#define S second 

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());  


void solve()
{
    
    int n;
    cin >> n;
    vector<int>v(n);
    for(int i = 0; i < n; i ++) cin >> v[i];


    clock_t st = clock();
    int ans = 0, itr = 100;
    while(itr --){
        random_shuffle(v.begin(), v.end());
        int x = 0, y = 0, a = (n + 1) / 2, b = n / 2;
        for(int i = 0; i < n; i ++){
            if(a == 0){
                y = __gcd(y, v[i]);
                b --;
            }
            else if(b == 0){
                x = __gcd(x, v[i]);
                a --;
            }

            else{
                if(__gcd(x, v[i]) == x){
                    a --;
                }

                else{
                    y = __gcd(y, v[i]);
                    b --;
                }
            }
        }
        ans = max(ans, x + y);

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



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

    int t  = 1;
    cin>>t;

    while(t--){

        solve();

    }

    return 0;

}

Information

Submit By
Type
Submission
Problem
P1077 Even Odd GCD (Hard Version)
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 17:20:55
Judged At
2024-11-11 03:11:55
Judged By
Score
4
Total Time
2ms
Peak Memory
320.0 KiB