/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 532.0 KiB
#2 Wrong Answer 2ms 324.0 KiB
#3 Accepted 2ms 532.0 KiB
#4 Wrong Answer 2ms 524.0 KiB
#5 Wrong Answer 2ms 320.0 KiB
#6 Wrong Answer 2ms 536.0 KiB
#7 Wrong Answer 2ms 532.0 KiB
#8 Wrong Answer 2ms 324.0 KiB
#9 Wrong Answer 2ms 532.0 KiB
#10 Wrong Answer 2ms 324.0 KiB
#11 Wrong Answer 2ms 324.0 KiB
#12 Wrong Answer 3ms 324.0 KiB
#13 Wrong Answer 4ms 320.0 KiB
#14 Wrong Answer 18ms 324.0 KiB
#15 Wrong Answer 286ms 732.0 KiB
#16 Wrong Answer 339ms 744.0 KiB
#17 Time Exceeded ≥2075ms ≥1.324 MiB
#18 Wrong Answer 12ms 324.0 KiB
#19 Wrong Answer 526ms 776.0 KiB
#20 Wrong Answer 516ms 776.0 KiB
#21 Wrong Answer 436ms 904.0 KiB
#22 Wrong Answer 446ms 844.0 KiB
#23 Wrong Answer 543ms 796.0 KiB
#24 Wrong Answer 511ms 812.0 KiB
#25 Wrong Answer 333ms 800.0 KiB
#26 Wrong Answer 616ms 816.0 KiB
#27 Wrong Answer 694ms 812.0 KiB
#28 Wrong Answer 637ms 824.0 KiB
#29 Wrong Answer 474ms 904.0 KiB
#30 Wrong Answer 1103ms 1.312 MiB
#31 Wrong Answer 1100ms 1.496 MiB
#32 Wrong Answer 244ms 728.0 KiB
#33 Wrong Answer 552ms 1.32 MiB
#34 Wrong Answer 227ms 740.0 KiB
#35 Time Exceeded ≥2085ms ≥1.32 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 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-10-03 13:22:17
Judged By
Score
4
Total Time
≥2085ms
Peak Memory
≥1.496 MiB