Submission #462598

#	Time	Username	Problem	Language	Result	Execution time	Memory
462598		training4usaco	Sirni (COCI17_sirni)	C++11	140 / 140	4275 ms	577072 KiB

sirni

#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair < int, int > ii;
 
const int N = 1e5 + 5;
const int M = 1e7 + 5;
 
int n;
int a[N], root[N], cnt[M], nxt[M];
vector < ii > v;
 
int f(int x) {
    if(x == root[x])
        return x;
    return root[x] = f(root[x]);
}
 
int main() {
 
    scanf("%d", &n);
 
    for(int i = 1; i <= n; i++)
        scanf("%d", a + i), root[i] = i;
 
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;
 
    for(int i = 1; i <= n; i++)
        nxt[a[i]] = i;
 
    nxt[M - 1] = n + 1;
    for(int i = M - 2; i >= 1; i--)
        if(!nxt[i])
            nxt[i] = nxt[i + 1];
 
    ll ans = 0;
 
    for(int i = n - 1; i >= 1; i--) {
        for(int j = a[i]; j < M; j += a[i]) {
            int k = nxt[j + (a[i] == j)];
            if(k > n)
                break;
            if(a[k] - j < a[i]) {
                cnt[a[k] - j]++;
                v.push_back({i, k});
            }
            else
                j = a[k] / a[i] * a[i] - a[i];
        }
    }
 
    for(int i = 1; i < M; i++)
        cnt[i] += cnt[i - 1];
 
    auto res = v;
 
    for(auto x : v)
        res[--cnt[a[x.second] % a[x.first]]] = x;
 
    for(auto x : res) {
        if(f(x.first) == f(x.second))
            continue;
        ans += a[x.second] % a[x.first];
        root[f(x.first)] = f(x.second);
    }
 
    printf("%lld\n", ans);
 
    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sirni.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d", a + i), root[i] = 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