Submission #711652

#	Time	Username	Problem	Language	Result	Execution time	Memory
711652		Pring	Slagalica (COCI19_slagalica2)	C++14	5 / 70	36 ms	4260 KiB

slagalica

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef std::pair<int, int> pii;

const int MXN = 100005;
int n;

struct P {
    bool l, r;
    int val;
    P() {
        l = false;
        r = false;
        val = 0;
    }
};

vector<P> LL, RR, LR, RL;
P first, last, br;
bool state, ff, fl;

bool check() {
    if (first.r && last.l && LR.size() != RL.size()) return false;
    if (first.r && !last.l && LR.size() != RL.size() - 1) return false;
    if (!first.r && last.l && LR.size() != RL.size() + 1) return false;
    if (!first.r && !last.l && LR.size() != RL.size()) return false;
    return true;
}

void OUT(vector<P> &v) {
    cout << v.back().val;
    state = v.back().r;
    v.pop_back();
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int type;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> type >> br.val;
        br.l = false, br.r = false;
        if (type == 3 || type == 4 || type == 8) br.l = true;
        if (type == 1 || type == 3 || type == 5) br.r = true;
        // cout << br.l << br.r << endl;
        if (type == 5 || type == 6) {
            if (ff) {
                cout << -1 << endl;
                return 0;
            }
            first = br;
            ff = true;
        }
        else if (type == 7 || type == 8) {
            if (fl) {
                cout << -1 << endl;
                return 0;
            }
            last = br;
            fl = true;
        } else (br.l ? (br.r ? RR : RL) : (br.r ? LR : LL)).push_back(br);
    }
    if (!ff || !fl) {
        cout << -1 << endl;
        return 0;
    }
    // cout << LL.size() << ' ' << LR.size() << ' ' << RL.size() << ' ' << RR.size() << endl;
    sort(LL.begin(), LL.end(), [](P a, P b) {
        return a.val < b.val;
    });
    sort(LR.begin(), LR.end(), [](P a, P b) {
        return a.val < b.val;
    });
    sort(RL.begin(), RL.end(), [](P a, P b) {
        return a.val < b.val;
    });
    sort(RR.begin(), RR.end(), [](P a, P b) {
        return a.val < b.val;
    });
    if (!check()) {
        cout << -1 << endl;
        return 0;
    }
    state = first.r;
    cout << first.val;
    for (int i = 1; i < n - 1; i++) {
        // cout << state << endl;
        cout << ' ';
        if (state) { // R
            if (RL.empty()) OUT(RR);
            else if (RR.empty()) OUT(RL);
            else if (LL.empty() && LR.empty()) OUT(RR);
            else OUT((RL.back().val < RR.back().val ? RR : RL));
        } else { // L
            if (LL.empty()) OUT(LR);
            else if (LR.empty()) OUT(LL);
            else if (RL.empty() && RR.empty()) OUT(LL);
            else OUT((LL.back().val < LR.back().val ? LR : LL));
        }
    }
    cout << ' ' << last.val << endl;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5