Submission #711769

#	Time	Username	Problem	Language	Result	Execution time	Memory
711769		Luicosas	Slagalica (COCI19_slagalica2)	C++17	65 / 70	37 ms	3028 KiB

slagalica

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5