oj.uz

Submission #1057641

# Submission time Handle Problem Language Result Execution time Memory
1057641 2024-08-14T02:16:05 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 681 ms 622260 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 50 ms 279388 KB Output is correct
2 Correct 70 ms 279892 KB Output is correct
3 Correct 52 ms 279376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 236372 KB Output is correct
2 Correct 170 ms 276564 KB Output is correct
3 Correct 50 ms 279644 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 279640 KB Output is correct
2 Correct 49 ms 277848 KB Output is correct
3 Correct 51 ms 279636 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 255952 KB Output is correct
2 Correct 101 ms 288680 KB Output is correct
3 Correct 67 ms 260036 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 246300 KB Output is correct
2 Correct 70 ms 265844 KB Output is correct
3 Correct 57 ms 251076 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 267468 KB Output is correct
2 Correct 118 ms 301160 KB Output is correct
3 Correct 72 ms 258500 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 243152 KB Output is correct
2 Correct 116 ms 292120 KB Output is correct
3 Correct 68 ms 258040 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 327376 KB Output is correct
2 Correct 505 ms 527732 KB Output is correct
3 Correct 105 ms 329932 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 327632 KB Output is correct
2 Correct 681 ms 622260 KB Output is correct
3 Correct 119 ms 333740 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 312000 KB Output is correct
2 Correct 678 ms 601800 KB Output is correct
3 Correct 73 ms 259888 KB Output is correct