Submission #1106876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106876		vjudge1	Sirni (COCI17_sirni)	C++17	140 / 140	971 ms	616356 KiB

sirni

#include<bits/stdc++.h>
#pragma GCC optimize("03,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "code"

const int ar = 1e5 + 5;
const int N = 1e7 + 2;
const ll mod = 1e9 + 7;
int n;
int maxn = 0;
int a[ar];
int root[ar];
int sz[ar];
vector<pair<int, int>> it;
vector<pair<int, int>> edge[N];
int ok[N];
int Next[N];
ll ans = 0;
int find_root(int a)
{
    if (a == root[a]) return a;

    root[a] = find_root(root[a]);
    return root[a];
}
void merge_set(int a, int b, int val)
{
    a = find_root(a);
    b = find_root(b);

    if (a != b)
    {
        ans += val;

        if (sz[a] < sz[b]) swap(a, b);

        sz[a] += sz[b];
        root[b] = a;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    it.push_back({0, 0});
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        root[i] = i;
        sz[i] = 1;
        cin >> a[i];
        maxn = max(maxn, a[i]);

        if (ok[a[i]])
        {
            merge_set(ok[a[i]], i, 0);
        }

        else
        {
            ok[a[i]] = i;
            it.push_back({a[i], i});
        }
    }

    sort(it.begin(), it.end());

    for (int i = 0; i < it.size() - 1; i++)
    {
        for (int j = it[i].fi + 1; j <= it[i + 1].fi; j++) Next[j] = it[i + 1].se;
    }

    for (int i = 1; i < it.size(); i++)
    {
        for (int j = it[i].fi; j <= maxn; j += it[i].fi)
        {
            int pos = Next[j];

            if (j == it[i].fi) pos = Next[j + 1];

            if (pos == 0) break;

            if (a[pos] >= (it[i].fi + j)) continue;

            edge[a[pos] % it[i].fi].push_back({it[i].se, pos});

        }
    }

    //sort(edge.begin(),edge.end());
    for (int i = 0; i <= maxn; i++)
    {
        for (auto p : edge[i])
        {
            int u = p.fi;
            int v = p.se;
            merge_set(u, v, i);
        }
    }

    cout << ans;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < it.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~
sirni.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 1; i < it.size(); i++)
      |                     ~~^~~~~~~~~~~
sirni.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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