oj.uz

Submission #711765

# Submission time Handle Problem Language Result Execution time Memory
711765 2023-03-17T12:45:53 Z Luicosas Slagalica (COCI19_slagalica2) C++17
65 / 70
 36 ms 3036 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define prv(x) for(auto& i : x) cout << i << " "; cout << "\n";
#ifdef LOCAL
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& i : {__VA_ARGS__}) cerr << i << " "; cerr << "\n";
#else 
#define debug(...)
#endif

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

    ll n;
    cin >> n;

    ll st = -1, en = -1, stv = -1, env = -1;
    vector<ll> zz, oo, zo, oz;
    for(ll i = 0; i < n; i++) {
        ll t, v;
        cin >> t >> v;
        if(t == 1) {
            zo.pb(v);
        } else if(t == 2) {
            zz.pb(v);
        } else if(t == 3) {
            oo.pb(v);
        } else if(t == 4) {
            oz.pb(v);
        } else if(t == 5) {
            st = 1;
            stv = v;
        } else if(t == 6) {
            st = 0;
            stv = v;
        } else if(t == 7) {
            en = 0;
            env = v;
        } else if(t == 8) {
            en = 1;
            env = v;
        }
    }

    function<bool(ll,ll,ll,ll,ll,ll)> ispos = [&](ll s, ll e, ll zzs, ll oos, ll zos, ll ozs) {
        bool pos = 1;
        pos &= (zzs >= 0);
        pos &= (ozs >= 0);
        pos &= (oos >= 0);
        pos &= (zos >= 0);
        if(s == e) {
            pos &= (zos == ozs);
            if(s == 0 && oos > 0) {
                pos &= (zos > 0);
            }
            if(s == 1 && zzs > 0) {
                pos &= (ozs > 0);
            }
        } else if(s == 1) {
            pos &= (ozs - zos) > 0;
        } else {
            pos &= (zos - ozs) > 0;
        }
        return pos;
    };

    if(!ispos(st,en, sz(zz), sz(oo), sz(zo), sz(oz))) {
        cout << -1 << "\n";
        return 0;
    }

    sort(itr(zz), greater<ll>());
    sort(itr(oo), greater<ll>());
    sort(itr(zo), greater<ll>());
    sort(itr(oz), greater<ll>());
    
    vector<ll> ans;
    for(ll i = 0, p = st; i < n - 2; i++) {
        array<ll,2> mnopt = {INT_MAX, -1};
        if(p == 0 && ispos(0, en, sz(zz) - 1, sz(oo), sz(zo), sz(oz))) {
            mnopt = min(mnopt, {zz.back(), 0});
        }
        if(p == 1 && ispos(1, en, sz(zz), sz(oo) - 1, sz(zo), sz(oz))) {
            mnopt = min(mnopt, {oo.back(), 1});
        }
        if(p == 0 && ispos(1, en, sz(zz), sz(oo), sz(zo) - 1, sz(oz))) {
            mnopt = min(mnopt, {zo.back(), 2});
        }
        if(p == 1 && ispos(0, en, sz(zz), sz(oo), sz(zo), sz(oz) - 1)) {
            mnopt = min(mnopt, {oz.back(), 3});
        }
        ans.pb(mnopt[0]);
        if(mnopt[1] == 0) {
            p = 0;
            zz.pop_back();
        }
        if(mnopt[1] == 1) {
            p = 1;
            oo.pop_back();
        }
        if(mnopt[1] == 2) {
            p = 1;
            zo.pop_back();
        }
        if(mnopt[1] == 3) {
            p = 0;
            oz.pop_back();
        }
    }
    cout << stv << " ";
    for(ll i : ans) {
        cout << i << " ";
    }
    cout << env << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2620 KB Output is correct
2 Correct 20 ms 1220 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2600 KB Output is correct
2 Correct 20 ms 1228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1232 KB Output is correct
2 Correct 29 ms 2784 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1148 KB Output is correct
2 Correct 25 ms 2548 KB Output is correct
3 Correct 36 ms 2884 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2616 KB Output is correct
2 Correct 19 ms 1272 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2556 KB Output is correct
2 Correct 19 ms 1232 KB Output is correct
3 Correct 30 ms 2760 KB Output is correct

Subtask #9
0 / 5.0

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

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3036 KB Output is correct
2 Correct 13 ms 1228 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2640 KB Output is correct
2 Correct 15 ms 1232 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2856 KB Output is correct
2 Correct 15 ms 1228 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2500 KB Output is correct
2 Correct 13 ms 1260 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2528 KB Output is correct
2 Correct 15 ms 1108 KB Output is correct