Submission #1122387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122387		dosts	Sirni (COCI17_sirni)	C++17	98 / 140	4251 ms	786432 KiB

sirni

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;
 
 
struct DSU {
    vi dad,sz;
 
    DSU(int nn) {
        dad.resize(nn+1);
        iota(all(dad),0ll);
        sz.assign(nn+1,1);
    }
 
    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }
 
    void unite(int x,int y) {
        int a = find(x),b = find(y);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a,b);
        dad[b] = a;
        sz[a]+=sz[b];
    }
};
 
vi have[10000001];
int orig[10000001];
 
struct Edge {
    int u,v;
};
 
void solve() {
    int n;
    cin >> n;
    vi p(n);
    for (int i=0;i<n;i++) cin >> p[i];
    sort(p.begin(),p.end());
    vi pp;
    for (int i = 0;i<n;i++) if (!i || p[i] != p[i-1]) pp.push_back(p[i]);
    n = pp.size();
    for (int i = 0;i<n;i++) {
        orig[pp[i]] = i+1;
    }
    int sm = 0;
    for (int i = 1;i<n;i++) sm+=pp[i]%pp[i-1];
    vi collect;
    vector<Edge> edges;
    int lasttake[n+1]{0};
    long long ans = 0;
    for (int i = 1;i<=10000000;i++) {
        for (auto it : have[i]) {
            if (!lasttake[it]) collect.push_back(it);
            lasttake[it] = i;
        }
        //cout << "I" sp i << endl;
        if (orig[i]) {
            if (!lasttake[orig[i]]) collect.push_back(orig[i]);
            lasttake[orig[i]] = i;
            have[i].push_back(orig[i]);
            //for (auto it : collect) cout << it.ff sp it.ss << '\n';
            for (auto it : collect) {
                if (it != orig[i]) {
                    if (edges.size() < 30000000 && i-lasttake[it] <= sm) edges.push_back(Edge{it,orig[i]});
                }
            }
            for (auto it : collect) lasttake[it] = 0;
            collect.clear();
            if (!lasttake[orig[i]]) collect.push_back(orig[i]);
            lasttake[orig[i]] = i;
        }
        for (auto it : have[i]) {
            if (i+pp[it-1] <= 10000000) have[i+pp[it-1]].push_back(it);
        }
        have[i].clear();
    }
 
    sort(all(edges),[&](const Edge& e1,const Edge& e2) {
        return pp[e1.v-1]%pp[e1.u-1] < pp[e2.v-1]%pp[e2.u-1];
    });
    DSU dsu(n);
    for (auto& it : edges) {
        if (dsu.find(it.u) != dsu.find(it.v)) {
            dsu.unite(it.u,it.v);
            ans+=pp[it.v-1]%pp[it.u-1];
        }
    }
    cout << ans << '\n';
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

sirni.cpp:12:23: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | int MOD = 1e9+7,inf = 2e18;
      |                       ^~~~

• 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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14