Submission #1207087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207087		racsosabe	Sirni (COCI17_sirni)	C++17	140 / 140	1266 ms	452200 KiB

sirni

#include<bits/stdc++.h>
using namespace::std;

const int N = 100000 + 5;
const int MAX = 10000000 + 2;
const int MAX_EDGES = 115129254 + 2;

int n;
int e;
int par[N];
int sizes[N];
int R[MAX];
int head[MAX];
int sorted_edges[MAX_EDGES];
pair<int, int> edges[MAX_EDGES];

int get(int x) {
    return par[x] == x ? x : par[x] = get(par[x]);
}

void join(int a, int b) {
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sizes[a] > sizes[b]) swap(a, b);
    par[a] = b;
    sizes[b] += sizes[a];
}

int get_cost(int x, int y) {
    return min(x % y, y % x);
}

void init(vector<int> &a) {
    int at = (int)a.size() - 1;
    int last = -1;
    for(int i = MAX - 1; i >= 0; i--) {
        if(at >= 0 and a[at] == i) {
            last = at;
            at--;
        }
        R[i] = last;
    }
}

void get_edges(vector<int> &a) {
    init(a);
    int maximum = a.back();
    for(int i = 0; i < n; i++) {
        int x = a[i];
        int last_taken = -1;
        if(R[x + 1] != last_taken) {
            edges[e].first = i;
            edges[e++].second = R[x + 1];
            last_taken = R[x + 1];
        }
        for(int l = x + x; l <= maximum; l += x) {
            int to = R[l];
            if(to != last_taken) {
                edges[e].first = i;
                edges[e++].second = to;
                last_taken = to;
            }
        }
    }
    for(int i = 0; i < e; i++) {
        int u, v;
        tie(u, v) = edges[i];
        head[get_cost(a[u], a[v])]++;
    }
    int sum = 0;
    for(int i = 0; i <= maximum; i++) {
        sum += head[i];
        head[i] = sum - head[i];
    }
    for(int i = 0; i < e; i++) {
        int u, v;
        tie(u, v) = edges[i];
        int val = get_cost(a[u], a[v]);
        sorted_edges[head[val]++] = i;
    }
}

long long solve(vector<int> &a) {
    get_edges(a);
    for(int i = 0; i < n; i++) {
        par[i] = i;
        sizes[i] = 1;
    }
    long long res = 0;
    for(int i = 0; i < e; i++) {
        int u, v;
        tie(u, v) = edges[sorted_edges[i]];
        if(get(u) != get(v)) {
            res += get_cost(a[u], a[v]);
            join(u, v);
        }
    }
    return res;
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = a.size();
    cout << solve(a) << '\n';
    return 0;
}

• 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