oj.uz

Submission #462598

# Submission time Handle Problem Language Result Execution time Memory
462598 2021-08-10T22:08:16 Z training4usaco Sirni (COCI17_sirni) C++11
140 / 140
 4275 ms 577072 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 78568 KB Output is correct
2 Correct 130 ms 81660 KB Output is correct
3 Correct 98 ms 78784 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 78656 KB Output is correct
2 Correct 107 ms 79676 KB Output is correct
3 Correct 97 ms 78696 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 78672 KB Output is correct
2 Correct 94 ms 78572 KB Output is correct
3 Correct 96 ms 78652 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 96068 KB Output is correct
2 Correct 352 ms 140684 KB Output is correct
3 Correct 208 ms 103416 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 81116 KB Output is correct
2 Correct 248 ms 112984 KB Output is correct
3 Correct 182 ms 96400 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 116192 KB Output is correct
2 Correct 419 ms 158292 KB Output is correct
3 Correct 207 ms 101768 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 84756 KB Output is correct
2 Correct 401 ms 154136 KB Output is correct
3 Correct 194 ms 100576 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 99080 KB Output is correct
2 Correct 2111 ms 438108 KB Output is correct
3 Correct 309 ms 103292 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 99188 KB Output is correct
2 Correct 3913 ms 577072 KB Output is correct
3 Correct 346 ms 110708 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 81840 KB Output is correct
2 Correct 4275 ms 574492 KB Output is correct
3 Correct 220 ms 103940 KB Output is correct