oj.uz

Submission #711647

# Submission time Handle Problem Language Result Execution time Memory
711647 2023-03-17T10:34:49 Z scottchou Slagalica (COCI19_slagalica2) C++17
70 / 70
 33 ms 2500 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 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 328 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 29 ms 2296 KB Output is correct
2 Correct 14 ms 1108 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2192 KB Output is correct
2 Correct 13 ms 1128 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1024 KB Output is correct
2 Correct 26 ms 2088 KB Output is correct
3 Correct 30 ms 2340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2064 KB Output is correct
2 Correct 14 ms 1104 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2160 KB Output is correct
2 Correct 13 ms 1088 KB Output is correct
3 Correct 27 ms 2184 KB Output is correct

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2492 KB Output is correct
2 Correct 12 ms 980 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2108 KB Output is correct
2 Correct 14 ms 1108 KB Output is correct

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2260 KB Output is correct
2 Correct 20 ms 1100 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2308 KB Output is correct
2 Correct 14 ms 1108 KB Output is correct