oj.uz

Submission #1106876

# Submission time Handle Problem Language Result Execution time Memory
1106876 2024-10-31T08:29:10 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 971 ms 616356 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 62 ms 279256 KB Output is correct
2 Correct 85 ms 279880 KB Output is correct
3 Correct 63 ms 279420 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 236616 KB Output is correct
2 Correct 214 ms 276552 KB Output is correct
3 Correct 67 ms 279624 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 279600 KB Output is correct
2 Correct 61 ms 277840 KB Output is correct
3 Correct 66 ms 279472 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 255952 KB Output is correct
2 Correct 152 ms 289956 KB Output is correct
3 Correct 90 ms 260544 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 246088 KB Output is correct
2 Correct 97 ms 265824 KB Output is correct
3 Correct 72 ms 251844 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 271792 KB Output is correct
2 Correct 161 ms 305756 KB Output is correct
3 Correct 84 ms 259992 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 243164 KB Output is correct
2 Correct 166 ms 294324 KB Output is correct
3 Correct 94 ms 258496 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 327364 KB Output is correct
2 Correct 811 ms 529152 KB Output is correct
3 Correct 168 ms 329924 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 327620 KB Output is correct
2 Correct 971 ms 616356 KB Output is correct
3 Correct 186 ms 333516 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 311772 KB Output is correct
2 Correct 953 ms 602800 KB Output is correct
3 Correct 87 ms 260288 KB Output is correct