Submission #1167961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167961		Saul0906	Sirni (COCI17_sirni)	C++20	56 / 140	697 ms	851968 KiB

sirni

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;

using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;

#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()

#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)

bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { if(n<0) return 0; return (n*(n+1))/2; }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 1e18;

struct DSU {
    
    vll pa;
    ll n, gr;

    DSU (ll n): n(n), gr(n), pa(n+2, 0) { fo (i, n+2) pa[i] = i; }

    ll find (ll i) { return pa[i] == i ? i : pa[i] = find(pa[i]); }
    void unite (ll i, ll j) {
        i = find(i);
        j = find(j);
        if (i == j) return;
        if (i > j) swap(i, j);
        gr--;
        pa[j] = i;
    }

};

void test_case () {
    ll n;
    cin >> n;
    vll a(n);
    fo (i, n) cin >> a[i];
    sort(all(a));
    a.erase(unique(all(a)), a.end());
    n = sz(a);
    ll mx = *max_element(all(a));
    vll idx(mx+1, -1), vis(n+1, -1);
    vector<vll> cmps;
    fo (i, n) idx[a[i]] = i;
    if (a[0] == 1 || n == 1) {
        cout << "0\n";
        return; 
    }

    {DSU ok(n);
        for (ll i = 1; i <= mx; i++) {
            if (idx[i] == -1) continue;
            for (ll j = 2*i; j <= mx; j += i) {
                if (idx[j] == -1) continue;
                ok.unite(idx[i], idx[j]);
            }
        }
        ll id = 0;
        fo (i, n) {
            ll j = ok.find(i);
            if (vis[j] == -1 ) vis[j] = id++, cmps.pb({});
            cmps[vis[j]].pb(i);
        }
    }
    ll ans = 0;
    while (sz(cmps) > 1) {
        vector<vector<pll>> prv(mx+2, vpll(2, mp(-1, -1))), nxt(mx+2, vpll(2, mp(-1, -1)));
        vll st(mx+2, -1);
        vector<array<ll, 2>> mul(mx+2, {-1, -1});
        fo (c, sz(cmps)) {
            for (ll i: cmps[c]) {
                st[a[i]] = c; 
                for (ll j = a[i]; j <= mx; j += a[i]) {
                    if (mul[j][0] == -1) mul[j][0] = c;
                    else mul[j][1] = c;
                }
            }
        }
        fore (i, 1, mx+1) {
            if (min(mul[i][0], mul[i][1]) > -1 && mul[i][0] != mul[i][1]) {
                prv[i] = {{i, mul[i][0]}, {i, mul[i][1]}};
                continue;
            }
            prv[i] = prv[i-1];
            if (mul[i][0] == -1) continue;
            prv[i][0] = {i, mul[i][0]};
            if (mul[i][0] != prv[i-1][0].se) {
                prv[i][1] = prv[i-1][0];
            }
        }
        forex (i, mx+1, 1) {
            nxt[i] = nxt[i+1];
            if (st[i] == -1) continue;
            nxt[i][0] = {i, st[i]};
            if (st[i] != nxt[i+1][0].se)
                nxt[i][1] = nxt[i+1][0];
        }
        DSU ok(sz(cmps));
        fo (c, sz(cmps)) {
            array<ll, 2> bst = {INF, -1};
            for (ll i: cmps[c]) {
                for (ll j = a[i]; j <= mx; j += a[i]) {
                    pll p = {-1, -1};
                    if (nxt[j][0].se != c) p = nxt[j][0];
                    else p = nxt[j][1];
                    if (p == mp(-1ll, -1ll)) continue;
                    if (p.fi-j < bst[0])
                        bst = {p.fi-j, p.se};
                }
                pll p = {-1, -1};
                if (prv[a[i]][0].se != c) p = prv[a[i]][0];
                else p = prv[a[i]][1];
                if (p == mp(-1ll, -1ll)) continue;
                if (a[i]-p.fi < bst[0])
                    bst = {a[i]-p.fi, p.se};
            }
            if (bst[1] >= 0 && ok.find(c) != ok.find(bst[1])) {
                ans += bst[0];
                ok.unite(c, bst[1]);
            }
        }
        if (ok.gr == 1) break;
        vis = vll(sz(cmps), -1);
        vector<vll> ncmps(ok.gr);
        ll id = 0;
        fo (c, sz(cmps)) {
            ll nc = ok.find(c);
            if (vis[nc] == -1 ) vis[nc] = id++;
            for (ll i: cmps[c]) {
                ncmps[vis[nc]].pb(i);
            }
        }
        cmps = ncmps;
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    while (tt--) test_case();
}

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