oj.uz

Submission #1095500

# Submission time Handle Problem Language Result Execution time Memory
1095500 2024-10-02T12:37:40 Z 0pt1mus23 Sirni (COCI17_sirni) C++14
0 / 140
 4180 ms 313776 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<  
const int   mod = 1e9+7 ,
            sze= 1e7 +23 ,
            inf = INT_MAX ,
            L = 31 ;

void opt1z(){
    int n;
    cin>>n;
    int ans=0;

    vector<int> arr(n);
    set<int> lst;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        lst.ins(arr[i]);
    }
    int mx = (*lst.rbegin()) *2;

    map<int,int> var;
    map<int,int> var2;
    set<int> near;
    set<int> near2;
    for(auto v:lst){
        int c = v;
        near2.ins(v);
        var2[v]++;
        while(c<=mx){
            var[c]++;
            near.ins(c);
            c+=v;
        }
    }
    sort(all(arr));
    map<int,int> cevap;
    vector<int> yux;
    map<int,int> bagla;
    for(auto v:arr){
        if(cevap.find(v)!=cevap.end() || bagla.count(v)){
            continue;
        }
        if(var[v]==1){
            near.erase(v);
        }
        auto it = near.upper_bound(v);
        int x = inf;
        if(it!=near.begin()){
            --it;
            // cout<<v _ ": " _ *it<<endl;
            x=v - *it;
            // cevap[v]=v-*it;
        }

        if(var[v]==1){
            near.ins(v);
        }

        int c= v;
        yux.clear();
        while(c<=mx){
            yux.pb(c);
            c+=v;
        }
        if(var2[v]==1){
            near2.erase(v);
        }
        int c2=-1;
        for(auto c:yux){
            auto it2 = near2.lower_bound(c);
            if(it2!=near2.end()){
                // cout<<v _ "=> " _ c _ *it2 - c<<endl;
                int y =  *it2 - c;
                if(y <= x){
                    x = y;
                    c2 = *it2;
                }
            }
        }

        if(var2[v]==1){
            near2.ins(v);
        }
        // cout<<v _ ":=> " _ x<<endl;

        if(x!=inf){
            cevap[v]=x;
            if(c2!=-1){
                bagla[c2]=1;
            }
            ans+=x;
        }
    }
    putr(ans);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1891 ms 111792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 31692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4180 ms 136012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 405 ms 32208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2930 ms 239044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3606 ms 313776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 39608 KB Output isn't correct
2 Halted 0 ms 0 KB -