oj.uz

Submission #949219

# Submission time Handle Problem Language Result Execution time Memory
949219 2024-03-19T03:53:00 Z vjudge1 Sirni (COCI17_sirni) C++17
98 / 140
 5000 ms 51780 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

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

    int n; cin >> n;
    vector <int> a(n);
    for ( auto &u: a ) cin >> u;
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
    n = a.size();
    int N = *max_element(all(a)) + 1;
    vector <int> fa(N);
    vector <ar<int,2>> nxt(n, {N, -1});
    vector <vector<int>> C(n);
    set <int> st;
    for ( int i = 0; i < n; i++ ){
        C[i].pb(i);
        st.insert(a[i]);
        fa[a[i]] = i;
    }
    int ans = 0;
    do{
        int c = 0;
        for ( auto &u: C ){
            c += !u.empty();
        }
        if ( c == 1 ) break;
        for ( int i = 0; i < n; i++ ){
            for ( auto &u: C[i] ){
                st.erase(a[u]);
            }
            assert(!st.empty());
            for ( auto &p: C[i] ){
                int u = a[p];
                for ( int j = u; j < N; j += u ){
                    auto it = st.lower_bound(j);
                    if ( it != st.end() ){
                        chmin(nxt[i], ar<int,2> {*it % j, fa[*it]});
                        chmin(nxt[fa[*it]], ar<int,2> {*it % j, i});
                    }
                    chmax(j, *it / j * j);
                }
            }
            for ( auto &u: C[i] ){
                st.insert(a[u]);
            }
        }
        auto upd = [&](int i, int j){
            for ( auto &u: C[j] ){
                fa[a[u]] = i;
                C[i].pb(u);
            } C[j].clear();
        };
        for ( int i = 0; i < n; i++ ){
            if ( C[i].empty() || nxt[i][1] == -1 ){
                nxt[i] = {N, -1};
                continue;
            }
            auto [w, j] = nxt[i];
            nxt[i] = {N, -1};
            if ( !C[j].empty() ){
                ans += w;
                if ( C[j].size() < C[i].size() ){
                    upd(i, j);
                } else upd(j, i);
            }
        }
    } while ( true );
    cout << ans;

    cout << '\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39516 KB Output is correct
2 Correct 285 ms 39524 KB Output is correct
3 Correct 13 ms 39516 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 2116 ms 39596 KB Output is correct
3 Correct 12 ms 39516 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39516 KB Output is correct
2 Correct 7 ms 39516 KB Output is correct
3 Correct 10 ms 39648 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 16096 KB Output is correct
2 Correct 2331 ms 15236 KB Output is correct
3 Correct 734 ms 13776 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6080 KB Output is correct
2 Correct 718 ms 5888 KB Output is correct
3 Correct 682 ms 12160 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1785 ms 16012 KB Output is correct
2 Correct 2444 ms 15512 KB Output is correct
3 Correct 898 ms 15700 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5452 KB Output is correct
2 Correct 2056 ms 13480 KB Output is correct
3 Correct 797 ms 14608 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 51780 KB Output is correct
2 Execution timed out 5031 ms 50624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 51600 KB Output is correct
2 Execution timed out 5056 ms 48980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 42064 KB Output is correct
2 Execution timed out 5049 ms 47708 KB Time limit exceeded
3 Halted 0 ms 0 KB -