제출 #248358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248358		NONAME	Sirni (COCI17_sirni)	C++14	140 / 140	4379 ms	681172 KiB

sirni

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int oo = int(1e7) + 1;
const int N = int(1e5) + 10;

int n, a[N], pr[N];
vector <pair <int, int> > g[oo];

int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }

int main() {
    //fast_io;

    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]), pr[i] = i;

    sort(a, a + n);

    for (int i = 0; i < n - 1; ++i) {
        if (a[i] == a[i + 1])
            g[0].push_back(make_pair(i, i + 1));

        for (int j = a[i]; j <= oo; j += a[i]) {
            int p = lower_bound(a, a + n, (j == a[i] ? j + 1 : j)) - a;

            if (p == n)
                break;

            while (j <= a[p])
                j += a[i];

            j -= a[i];
            g[a[p] - j].push_back(make_pair(i, p));
        }
    }

    ll ans = 0;
    int kol = 0;
    for (int i = 0; i < oo; ++i)
    for (auto j : g[i]) {
        int x = f(j.first);
        int y = f(j.second);

        if (x == y)
            continue;

        ans += i;
        ++kol;
        if (kol == n - 1)
            return void(printf("%I64d\n", ans)), 0;
        pr[y] = x;
    }
}

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

sirni.cpp: In function 'int main()':
sirni.cpp:55:46: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
             return void(printf("%I64d\n", ans)), 0;
                                              ^
sirni.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
sirni.cpp:20:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]), pr[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