Submission #1167692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167692		Turkhuu	Sirni (COCI17_sirni)	C++20	140 / 140	845 ms	611512 KiB

sirni

//https://codeforces.com/blog/entry/50241?#comment-341952
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
 
int x[100000], nxt[10000001], p[10000001];
vector<pair<int, int> > w[10000001];
 
int P(int v){
    if (p[v])return p[v] = P(p[v]);
    return v;
}
 
int main(){
    int n;
    scanf("%d", &n);
    f(i, 0, n)scanf("%d", x + i), nxt[x[i]] = x[i];
    sort(x, x + n);
    n = unique(x, x + n) - x;
    for (int i = 9999999; i >= 0; --i)if (!nxt[i])nxt[i] = nxt[i + 1];
    f(i, 0, n){
        int t = x[i], z = nxt[t + 1];
        if (z && z - t < t)w[z - t].push_back(make_pair(t, z));
        for (int j = t << 1; j <= 10000000; j += t){
            z = nxt[j];
            if (!z)break;
            if (z - j < t)w[z - j].push_back(make_pair(t, z));
        }
    }
    ll an = 0;
    int k = 0;
    f(i, 0, 10000000){
        vector<pair<int, int> > &v = w[i];
        int s = v.size();
        f(j, 0, s){
            int x = P(v[j].first), y = P(v[j].second);
            if (x == y)continue;
            an += i;
            p[y] = x;
            if (++k + 1 == n)break;
        }
        if (k + 1 == n)break;
    }
    printf("%lld\n", an);
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sirni.cpp:18:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     f(i, 0, n)scanf("%d", x + i), nxt[x[i]] = x[i];
      |               ~~~~~^~~~~~~~~~~~~

• 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