oj.uz

Submission #711764

# Submission time Handle Problem Language Result Execution time Memory
711764 2023-03-17T12:43:15 Z Luicosas Slagalica (COCI19_slagalica2) C++17
65 / 70
 39 ms 3400 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);

    int n;
    cin >> n;

    int st = -1, en = -1, stv = -1, env = -1;
    vector<int> zz, oo, zo, oz;
    for(int i = 0; i < n; i++) {
        int 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(int,int,int,int,int,int)> ispos = [&](int s, int e, int zzs, int oos, int zos, int 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<int>());
    sort(itr(oo), greater<int>());
    sort(itr(zo), greater<int>());
    sort(itr(oz), greater<int>());
    
    vector<int> ans;
    for(int i = 0, p = st; i < n - 2; i++) {
        array<int,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(int 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 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3004 KB Output is correct
2 Correct 15 ms 1872 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2912 KB Output is correct
2 Correct 18 ms 1856 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2052 KB Output is correct
2 Correct 28 ms 3032 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1760 KB Output is correct
2 Correct 28 ms 2832 KB Output is correct
3 Correct 39 ms 3208 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2956 KB Output is correct
2 Correct 16 ms 1868 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2824 KB Output is correct
2 Correct 15 ms 1868 KB Output is correct
3 Correct 29 ms 3084 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 3136 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 35 ms 3388 KB Output is correct
2 Correct 16 ms 1748 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2948 KB Output is correct
2 Correct 14 ms 1748 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3400 KB Output is correct
2 Correct 21 ms 1872 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2912 KB Output is correct
2 Correct 14 ms 1868 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2972 KB Output is correct
2 Correct 15 ms 1916 KB Output is correct