Submission #711647

#	Time	Username	Problem	Language	Result	Execution time	Memory
711647		scottchou	Slagalica (COCI19_slagalica2)	C++17	70 / 70	33 ms	2500 KiB

slagalica

#include<bits/stdc++.h>
using namespace std;
int const N = 1e5 + 5;
vector<int> id[5];
int ans[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int x, a;
    int front = 0, back = 0;
    for(int i = 0; i < n; i++){
        cin >> x >> a;
        if(x == 5 || x == 6){
            if(front){
                cout << -1 << '\n';
                return 0;
            }
            front = x;
            ans[0] = a;
        }else if(x == 7 || x == 8){
            if(back){
                cout << -1 << '\n';
                return 0;
            }
            back = x;
            ans[n - 1] = a;
        }else{
            id[x].push_back(a);
        }
    }
    if(!front || !back){
        cout << -1 << '\n';
        return 0;
    }
    int num1 = id[1].size(), num4 = id[4].size();
    if(front == 5){
        if(back == 7){
            if(num4 != num1 + 1){
                cout << -1 << '\n';
                return 0;
            }
        }else{
            if(num4 != num1){
                cout << -1 << '\n';
                return 0;
            }
        }
    }else{
        if(back == 7){
            if(num4 != num1){
                cout << -1 << '\n';
                return 0;
            }
        }else{
            if(num1 != num4 + 1){
                cout << -1 << '\n';
                return 0;
            }
        }
    }
    for(int i = 1; i <= 4; i++){
        sort(id[i].begin(), id[i].end());
        reverse(id[i].begin(), id[i].end());
    }
    bool pre;
    int last0 = -1, last1 = -1;
    if(front == 5){
        pre = 1;
        last1 = 0;
    }else{
        pre = 0;
        last0 = 0;
    }
    int now;
    for(now = 1; now < n - 1; now++){
        int minn = -1, minid = 1e9 + 1;
        if(pre == 1){
            if(!id[3].empty() && id[3].back() < minid){
                minid = id[3].back();
                minn = 3;
            }
            if(!id[4].empty() && id[4].back() < minid){
                minid = id[4].back();
                minn = 4;
            }
            if(minn == -1)
                break;
            ans[now] = minid;
            if(minn == 4){
                pre = 0;
                last0 = now;
            }else{
                last1 = now;
            }
        }else{
            if(!id[1].empty() && id[1].back() < minid){
                minid = id[1].back();
                minn = 1;
            }
            if(!id[2].empty() && id[2].back() < minid){
                minid = id[2].back();
                minn = 2;
            }
            if(minn == -1)
                break;
            ans[now] = minid;
            if(minn == 1){
                pre = 1;
                last1 = now;
            }else{
                last0 = now;
            }
        }
        id[minn].pop_back();
    }
    for(int i = 0; i < now; i++){
        cout << ans[i] << ' ';
        if(last0 == i){
            while(!id[2].empty()){
                cout << id[2].back() << ' ';
                id[2].pop_back();
            }
        }
        if(last1 == i){
            while(!id[3].empty()){
                cout << id[3].back() << ' ';
                id[3].pop_back();
            }
        }
    }
    cout << ans[n - 1] << '\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: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5