oj.uz

Submission #887130

# Submission time Handle Problem Language Result Execution time Memory
887130 2023-12-13T20:53:57 Z Servant_of_the_Lord Sirni (COCI17_sirni) C++17
98 / 140
 5000 ms 611924 KB 
#include <bits/stdc++.h>
#pragma gcc optimize("Ofast")
#pragma gcc target("avx,avx2,sse4")
#define ll long long

using namespace std;

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll x,y,z,a,b,c;
    cin>>x;
    set<ll>s;
    map<ll,ll>m;
    for(ll i=0;i<x;i++)
    {
        cin>>y;
        s.insert(y);
        m[y]=i;
    }
    vector<vector<ll>>v(10'000'000);
    for(ll i:s)
    {
        if(v[i-1].empty())
        {
            for(ll j=i-1;j<10'000'000;j+=i)
            {
                v[j].push_back(i);
            }
        }
    }
    vector<ll>w(x,-1);
    function<ll(ll)>g=[&](ll a){return w[a]<0?a:w[a]=g(w[a]);};
    function<bool(ll,ll)>u=[&](ll a,ll b)
    {
        a=g(m[a]),b=g(m[b]);
        if(a==b)return false;
        if(w[a]>w[b])swap(a,b);
        w[a]+=w[b];
        w[b]=a;
        return true;
    };
    a=0;
    bitset<10'000'000>t;
    for(ll i=0;i<10'000'000;i++)
    {
        vector<ll>e;
        for(ll j:s)
        {
            for(ll k:v[j-i-1])
            {
                if(u(j,k))
                {
                    a+=i;
                }
            }
            if(j-i-1==0||t[j-i-1])e.push_back(j);
            t[j-i-1]=1;
        }
        for(ll j:e)s.erase(j);
    }
    cout<<a<<'\n';
}

Compilation message

sirni.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
sirni.cpp:3: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
    3 | #pragma gcc target("avx,avx2,sse4")
      | 
sirni.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~
sirni.cpp: In function 'int main()':
sirni.cpp:13:12: warning: unused variable 'z' [-Wunused-variable]
   13 |     ll x,y,z,a,b,c;
      |            ^
sirni.cpp:13:16: warning: unused variable 'b' [-Wunused-variable]
   13 |     ll x,y,z,a,b,c;
      |                ^
sirni.cpp:13:18: warning: unused variable 'c' [-Wunused-variable]
   13 |     ll x,y,z,a,b,c;
      |                  ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 236624 KB Output is correct
2 Correct 1270 ms 299536 KB Output is correct
3 Correct 345 ms 237136 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 372320 KB Output is correct
2 Correct 3645 ms 583628 KB Output is correct
3 Correct 304 ms 238416 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 236884 KB Output is correct
2 Correct 151 ms 236664 KB Output is correct
3 Correct 299 ms 236884 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1701 ms 408628 KB Output is correct
2 Correct 2747 ms 549884 KB Output is correct
3 Correct 2819 ms 595396 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 285184 KB Output is correct
2 Correct 2410 ms 428856 KB Output is correct
3 Correct 2310 ms 507672 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2613 ms 476084 KB Output is correct
2 Correct 2774 ms 611924 KB Output is correct
3 Correct 1800 ms 503820 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 458508 KB Output is correct
2 Correct 3109 ms 609344 KB Output is correct
3 Correct 2496 ms 572952 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1846 ms 285400 KB Output is correct
2 Execution timed out 5021 ms 559228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1853 ms 297388 KB Output is correct
2 Execution timed out 5047 ms 602872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 244760 KB Output is correct
2 Execution timed out 5044 ms 504496 KB Time limit exceeded
3 Halted 0 ms 0 KB -