Submission #1167268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167268		akulyat	Sirni (COCI17_sirni)	C++20	84 / 140	5110 ms	519352 KiB

sirni

#include <bits/stdc++.h>
#pragma GCC optimize ("O3", "unroll-all-loops")
#pragma GCC target ("sse4.2")

using namespace std;

#define F first
#define S second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (a).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long       ll;
typedef long double     ld;
typedef pair<ll, ll>   pll; 
typedef pair<int, int> pii; 
typedef pair<pii, pii> ppii; 

typedef vector<int> vi; 
typedef vector<ll> vll; 

const long long kk = 1000;
const long long ml = kk * kk;
const long long mod = ml * kk + 7;
const long long inf = ml * ml * ml + 7; 

template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.F >> p.S; }
template<class T, class U> inline ostream& operator<<(ostream& str, const pair<T, U> &p) { str << p.F << ' ' << p.S << ' '; return str; }
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
template<class T> inline ostream& operator<<(ostream& str, const vector<T> &a) { for (auto &i : a) str << i << ' '; return str; }

void flush() { cout << flush; }
void flushln() { cout << endl; }
template<class T> void read(T &x) { cin >> x; }
template<class T, class ...U> void read(T &x, U&... u) { read(x); read(u...); }
template<class T> void print(const T &x) { cout << x; }
template<class T, class ...U> void print(const T &x, const U&... u) { print(x); print(u...); }
template<class ...T> void println(const T&... u) { print(u..., '\n'); }
template<class T> void eprint(const T &x) { cerr << x; }
template<class T, class ...U> void eprint(const T &x, const U&... u) { eprint(x); eprint(u...); }
template<class ...T> void eprintln(const T&... u) { eprint(u..., '\n'); }

#ifdef DEBUG
    mt19937 rng(1033);
#else
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    
    #define cerr if(false)cerr
    #define eprintln if(false)eprintln
    #define eprint if(false)eprint
#endif
int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }


const int N = 500 * kk;

int n;
vector<int> v;

struct DSU {
    vector<int> p;
    vector<int> sz;
    DSU(int n) {
        p.assign(n, 0);
        sz.assign(n, 1);
        iota(all(p), 0);
    }

    int pp(int v) {
        if (p[v] == v)
            return v;
        return p[v] = pp(p[v]);
    }

    bool unite(int u, int v) {
        u = pp(u);
        v = pp(v);
        if (u == v)
            return false;
        if (sz[u] < sz[v])
            swap(u, v);
        p[u] = v;
        sz[u] += sz[v];
        return true;
    }
};


void solve() {
    cin >> n;
    v.resize(n);
    read(v);
    set<int> s(all(v));

    v.clear();
    for (auto i : s)
        v.push_back(i);
    n = v.size();

    // vector<int> where(v.back() + 1, -1);
    // for (int i = 0; i < n; i++)
    //     where[v[i]] = i;

    // vector<int> c(n);
    // iota(all(c), 0);
    // vector<vi> cc(n);
    // for (int i = 0; i < n; i++)
    //     cc[c[i]].push_back(i);

    const int N = v.back() + 1;
    DSU dsu(N);

    vi cp[N];
    int ps[n];

    auto fill_cp = [&]() {
        for (int i = 0; i < N; i++)
            cp[i].clear();
        for (int i = 0; i < n; i++) {
            int p = dsu.pp(v[i]);
            ps[i] = p;
            cp[p].push_back(v[i]);
        }
    };
    fill_cp();

    ll ans = 0;
    auto unite = [&](int a, int b) {
        if (!dsu.unite(a, b))
            return;
        ans += max(a, b) % min(a, b);
    };

    for (int it = 0; it < 20; it++) {
        vector<int> bst(N, mod);
        vector<pii> who(N, {-1, -1});

        vector<pii> nxt(N, {mod, mod});
        int pt = n - 1;
        for (int i = N - 1; i >= 0; i--) {
            if (i + 1 != N)
                nxt[i] = nxt[i + 1];
            if (pt != -1 && i == v[pt]) {
                if (nxt[i].F != mod && ps[nxt[i].F] == ps[pt]) {
                    nxt[i].F = pt;
                } else {
                    if (nxt[i].S != mod && ps[nxt[i].S] == ps[pt]) {
                        nxt[i].S = pt;
                    }
                    else {
                        nxt[i].S = pt;
                    }
                }
                pt--;
            }

            if (nxt[i].F > nxt[i].S)
                swap(nxt[i].F, nxt[i].S);
        }
        for (int p = 0; p < N; p++) {
            if (cp[p].empty())
                continue;
            // for (auto i : cp[p])
            //     s.erase(i);
            if (true) {
                for (auto i : cp[p]) {
                    for (int j = i; j < N; j += i) {
                        int lj = j;
                        if (lj == i)
                            lj++;
                        if (lj == N)
                            continue;
                        auto xi = nxt[lj].F;
                        if (xi == mod)
                            continue;
                        if (ps[xi] == p) {
                            continue;
                            // xi = nxt[j].S;
                            // if (xi == mod)
                            //     continue;
                        }

                        int x = v[xi];
                        int lval = abs(x - j);
                        int px = ps[xi];
                        // auto px = dsu.pp(x);

                        if (bst[p] > lval) {
                            bst[p] = lval;
                            who[p] = {i, x};
                        }
                        if (bst[px] > lval) {
                            bst[px] = lval;
                            who[px] = {x, i};
                        }


                        // auto z = s.lower_bound(j);
                        // if (z != s.end()) {
                        //     int x = *z;
                        //     int lval = abs(x - j);
                        //     auto px = dsu.pp(x);

                        //     if (bst[p] > lval) {
                        //         bst[p] = lval;
                        //         who[p] = {i, x};
                        //     }
                        //     if (bst[px] > lval) {
                        //         bst[px] = lval;
                        //         who[px] = {x, i};
                        //     }
                        // }
                    }
                }
            }
            // for (auto i : cp[p])
            //     s.insert(i);
        }
        for (int p = 0; p < N; p++) {
            if (who[p].F != -1) {
                unite(who[p].F, who[p].S);
            }
        }
        fill_cp();
    }


    println(ans);

    eprintln("\n\n\n");

}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int t = 1; 
    // cin >> t;
    while (t--)
        solve();

    #ifdef DEBUG
        cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
    #endif
}

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