Submission #1138086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138086		phamducminh	Sirni (COCI17_sirni)	C++20	126 / 140	3193 ms	786552 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, a[100009];
int ans=0, ans1=0, mx=0;



struct canh{
    int x, y, w;
};
// canh dscanh[10000009];
vector<pair<int,int>> dscanh[10000009];
int truoc[100009],rnk[100009];
vector<int> b;



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

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;
    if (rnk[u]<rnk[v]) swap(u,v);
    truoc[u]=v;
    rnk[u]+=rnk[v];

    return true;
}

bool cmp(canh a, canh b){
    return a.w < b.w;
}


void solve(){  

    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> a[i];
        b.push_back(a[i]);
        mx=max(mx,a[i]);
    }



    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(n+1);
    for (int i=1; i<=n; i++) {
        // for (int j=i+1; j<=n; j++) {
        //     int w = a[j] % a[i];
        //     dscanh.push_back({i, j, w});
        // }
    

        for (int m=a[i]; m<=mx; m+=a[i]){
            int it=lower_bound(a+i,a+n+1,m)-a;

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


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



    // 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 << min(ans,ans1);

}

    

• Subtask 1: 14 / 14
• Subtask 2: 0 / 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