/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 352.0 KiB
#2 Accepted 2ms 328.0 KiB
#3 Accepted 14ms 560.0 KiB
#4 Accepted 9ms 560.0 KiB
#5 Accepted 10ms 572.0 KiB
#6 Accepted 13ms 560.0 KiB
#7 Accepted 9ms 560.0 KiB
#8 Accepted 10ms 560.0 KiB
#9 Accepted 15ms 572.0 KiB
#10 Accepted 22ms 580.0 KiB
#11 Accepted 94ms 588.0 KiB
#12 Accepted 133ms 608.0 KiB
#13 Accepted 49ms 592.0 KiB
#14 Accepted 59ms 608.0 KiB
#15 Accepted 55ms 608.0 KiB
#16 Accepted 41ms 584.0 KiB
#17 Accepted 51ms 600.0 KiB
#18 Accepted 29ms 796.0 KiB
#19 Accepted 26ms 572.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
 
#define ll                      long long int
#define lld                     long double
//Ordered set(tree)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set             tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define multi_ordered_set       tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define mxheap                  priority_queue<ll>
#define mnheap                  priority_queue<ll, vector<ll>, greater<ll>>
#define mxheap2                 priority_queue<pair<ll,ll>>
#define mnheap2                 priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>
//Macros
#define FIO                     ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(NULL);
#define TC(t)                   int t; cin >> t; for(int i = 1; i <= t; i++)
#define ini(x, y)               memset(x, y, sizeof(x))
#define loop(i, a, b)           for(ll i = a; i <= b; i++)
#define loop2(i, b, a)          for(ll i = b; i >= a; i--)
#define pn                      cout << "NO\n";
#define py                      cout << "YES\n";
#define ed                      cout << "\n";
#define vrev(v)                 reverse(v.begin(),v.end());
#define vsort(v)                sort(v.begin(),v.end());
#define uni(v)                 v.erase(unique(v.begin(), v.end()), v.end()); // last it is like e set
#define vlowerB(v,x)            lower_bound(v.begin(), v.end(), x); 
#define vupperB(v,x)            upper_bound(v.begin(), v.end(), x); 
#define bits(x)                 __builtin_popcountll(x)
#define zrbits(x)               __builtin_ctzll(x)
//Constants
const ll M = 1e9 + 7;
const ll N = 1e5 + 5;
ll POW(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans = (ans * a) % M; a = (a * a) % M; b >>= 1; } return ans; }
/*  Contest time:
    1. Check it is binary searce or not.
    2. DP or not.
    3. Segment Tree of not
    4. Hash or not.
    5. Number theory   
*/

void solve(){
    int n; cin >> n ;
    int a[n+2];
    set < int > v[101];
    loop(i, 1, n) {
        int x; cin >> x;
        for(int j = 1; j*j <= x; j++){
            if(x%j == 0){
                v[j].insert(i); v[x/j].insert(i);
            }
        }
    }

    ll ans = 0;
    loop(i, 1, 100){
        loop(j, 1, 100){
            bool no = 0;
            loop(k, 1, n){
                if(v[i].count(k) || v[j].count(k));
                else {
                    no = 1; break;
                }
            }
            if(!no && v[i].size() >= n/2 && v[j].size() >= n/2){
                ans = max(ans, i+j);
            }
        }
    }
    cout << ans; ed
    
}
 
int main(){
    FIO
    TC(t) 
    solve();
    return 0;
}

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:18:50
Judged At
2024-10-03 13:22:43
Judged By
Score
100
Total Time
133ms
Peak Memory
796.0 KiB