제출 #637010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637010		nguyen31hoang08minh2003	Sirni (COCI17_sirni)	C++14	140 / 140	1427 ms	638396 KiB

sirni

/*
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
=\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/=
\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
 //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\
//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\
\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //
 \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\
=/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\=
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
=\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/=
\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
 //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\
//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\//    \\
\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //\\    //
 \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //  \\  //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\
=/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\=
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
=\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/=
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

struct DisjointSet {
private:
    mutable std::vector<int> r;
public:
    DisjointSet() {};
    DisjointSet(const int n): r(n, -1) {};

    void reload() {
        std::fill(r.begin(), r.end(), -1);
    };

    int getRoot(const int x) const {
        return r[x] < 0 ? x : (r[x] = getRoot(r[x]));
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (r[x] > r[y])
            std::swap(x, y);
        r[x] += r[y];
        r[y] = x;
        return true;
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int getTreeSize(const int x) const {
        return -r[getRoot(x)];
    }
};


const int maxN = 1e5 + 5, maxP = 1e7 + 7, inf = 0x3f3f3f3f, ninf = 0xc0c0c0c0;

int n, mxp, p[maxN], k[maxP];
DisjointSet dsu(maxP);
vii e[maxP];

void input() {
    cin >> n;
    fort(i, 1, n) {
        cin >> p[i];
        k[p[i]] = p[i];
        maxi(mxp, p[i]);
    }
}

void subtask1() {
    /**
        Prim algorithm

        min(x % y, y % x) = max(x, y) % min(x, y)

    **/
    const int N = n + 5;
    int x;
    ll res = 0;
    vi d(N, inf);
    vector<bool> vis(N);
    d[1] = 0;
    fort(_, 1, n) {
        x = -1;
        fort(i, 1, n) {
            if (vis[i])
                continue;
            if (x < 0 || d[x] > d[i])
                x = i;
        }
        vis[x] = true;
        res += d[x];
        fort(i, 1, n) {
            if (vis[i])
                continue;
            mini(d[i], min(p[x] % p[i], p[i] % p[x]));
        }
    }
    cout << res << '\n';
}

void subtask3() {
    ll res = 0;
    for (int i = mxp - 1, j; i >= 1; --i)
        if (!k[i])
            k[i] = k[i + 1];
        else {
            j = i << 1;
            if (i < mxp) {                           // for case i only add edge from i to a vertex with value in [i + 1, i * 2 - 1]
                if (j > mxp || k[i + 1] != k[j])     // check if there is a vertex with value in [i + 1, j - 1]
                    e[k[i + 1] - i].emplace_back(i, k[i + 1]);
            }
            for (; j <= mxp; j += i)                 // for case j = i * t (i >= 2), add edge from j to a vertex with value in [j, j + i - 1]
                if (j + i > mxp || k[j] != k[j + i]) // check if there is a vertex with value in [j, j + i - 1]
                    e[k[j] - j].emplace_back(i, k[j]);
        }
    fort(w, 0, mxp)
        for (const auto &[x, y] : e[w])
            if (dsu.unite(x, y))
                res += w;
    cout << res << '\n';
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    input();
    if (n <= 7500)
        subtask1();
    else
        subtask3();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sirni.cpp: In function 'void subtask3()':
sirni.cpp:155:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |         for (const auto &[x, y] : e[w])
      |                          ^

• 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