Submission #1138088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138088		phamducminh	Sirni (COCI17_sirni)	C++20	140 / 140	4247 ms	577236 KiB

sirni

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
#include <random>
#include <sstream>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("Ofast","inline","no-stack-protector")
// #pragma GCC target("arch=skylake")

using namespace std;

#define file(name) freopen(name".inp","r",stdin);\
                    freopen(name".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define all1(a) a+1,a+n+1
#define ll long long

const long long INF=1e18;
const long long MOD=1e9+7;
const long long MODD[] = {(long long)998244353,(long long)1e9+2277, (long long)1e9+5277}; // 998244353
const int maxN=2e5+9;
const long long LOG=19;
const double eps = 1e-1;


//------------------------



void solve();
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


    // file("PNUM");



    int t;

    // cin >> t;

    t=1;

    while (t--){
        solve();
    }

    cerr << "Time: " << TIME << "s.\n";
    cerr << "ducminh";
    return 0;
}

/// -------------- PROBLEM SOLUION --------------------



int n;
int ans=0, ans1=0, mx=0;




// canh dscanh[10000009];
vector<pair<int,int>> dscanh[10000009];
int truoc[10000009];
// vector<int> b;



void init(int n){
    for(int i=1; i<=n; i++){
        truoc[i] = i;
    }
}

int root(int u){
    if (truoc[u]==u) return u;
    return truoc[u]=root(truoc[u]);
}


bool hop(int x, int y){
    int u=root(x), v=root(y);

    if (u==v) return false;
    truoc[v]=u;

    return true;
}




void solve(){  

    cin >> n;
    set<int> b;
    for (int i=1; i<=n; i++){
        int x;
        cin >> x;
        b.insert(x);
        mx=max(mx,x);
    }



    // sort(all(b));
    // b.resize(unique(all(b)) - b.begin());
 
    // for(int i=0; i<b.size(); i++)
    //     a[i+1] = b[i];
    n=b.size();
    
    if (n == 1) return cout << 0, void();
    // if (a[1] == 1) return cout << 0, void();
    


    // sort(a+1,a+n+1);

    // for (int i=2; i<=n; i++){
    //     ans+=min(a[1]%a[i], a[i]%a[1]);
    // }

    // if (n>1000) return cout << 0, void();


    int ti=0;
    init(mx+1);
    for (int i: b) {
        // for (int j=i+1; j<=n; j++) {
        //     int w = a[j] % a[i];
        //     dscanh.push_back({i, j, w});
        // }

        auto it=b.upper_bound(i);

        if (it == b.end()) continue;
        dscanh[*it-i].push_back({i,*it});

        for (int m=2*i; m<=mx; m+=i){
            auto it=b.lower_bound(m);

            // if (it>n || it<1) continue;
            // if (m==a[i] && a[it]==a[i]) it++;
            // if (it>n || it<1) continue;

            if (it == b.end()) continue;

            // dscanh.push_back({i, it, a[it]-m});
            // dscanh[ti++]={i,it,a[it]-m};
            dscanh[*it%i].push_back({i,*it});
            m = *it / i * i;
        }
    }



    // sort(dscanh, dscanh+ti, cmp);

    int d1=0;
    for (int i=0; i<=mx; i++){

        for (pair<int,int> tmp: dscanh[i]) {
            if (hop(tmp.first, tmp.second)){
                ans1 += i;
                d1++;
                if (d1==n-1) break;
            }
        }
    }






    cout << ans1;

}

    

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14