oj.uz

Submission #402280

# Submission time Handle Problem Language Result Execution time Memory
402280 2021-05-11T14:04:35 Z jenkinsser Slagalica (COCI19_slagalica2) C++17
20 / 70
 1000 ms 15548 KB 
#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 1e5+5;
const int INF = 1e9+5;
const int mod = 1e9+7;

int n,ans[N];
multiset<int> s[9];

void solve(int pos,int cur){
    if(pos==n){
        if(s[7].size()){
            if(cur==2||cur==4||cur==6)
                ans[n]=*s[7].begin();
            else
                return;
        }
        else{
            if(cur==1||cur==3||cur==5)
                ans[n]=*s[8].begin();
            else
                return;
        }
        for(int i=1;i<=n;i++)
            cout << ans[i] << sp;
        exit(0);
    }
    if(cur==1||cur==3||cur==5){
        if(s[3].empty()&&s[4].empty())
            return;
        if(s[4].empty()){
            int a=*s[3].begin(); 
            ans[pos]=a;
            s[3].erase(s[3].begin());
            solve(pos+1,3);
            s[3].insert(a);
            return;
        }
        if(s[3].empty()){
            int b=*s[4].begin();           
            ans[pos]=b;
            s[4].erase(s[4].begin());
            solve(pos+1,4);
            s[4].insert(b);
            return;
        }
        int a=*s[3].begin(); 
        int b=*s[4].begin();
        if(a<b){
            ans[pos]=a;
            s[3].erase(s[3].begin());
            solve(pos+1,3);
            s[3].insert(a);
            ans[pos]=b;
            s[4].erase(s[4].begin());
            solve(pos+1,4);
            s[4].insert(b);
        }
        else{
            ans[pos]=b;
            s[4].erase(s[4].begin());
            solve(pos+1,4);
            s[4].insert(b);
            ans[pos]=a;
            s[3].erase(s[3].begin());
            solve(pos+1,3);
            s[3].insert(a);
        }
    }
    else if(cur==2||cur==4||cur==6){
        if(s[1].empty()&&s[2].empty())
            return;
        if(s[2].empty()){
            int a=*s[1].begin();
            ans[pos]=a;
            s[1].erase(s[1].begin());
            solve(pos+1,1);
            s[1].insert(a);
            return;
        }
        if(s[1].empty()){  
            int b=*s[2].begin();          
            ans[pos]=b;
            s[2].erase(s[2].begin());
            solve(pos+1,2);
            s[2].insert(b);
            return;
        }
        int a=*s[1].begin();
        int b=*s[2].begin();
        if(a<b){
            ans[pos]=a;
            s[1].erase(s[1].begin());
            solve(pos+1,1);
            s[1].insert(a);
            ans[pos]=b;
            s[2].erase(s[2].begin());
            solve(pos+1,2);
            s[2].insert(b);
        }
        else{
            ans[pos]=b;
            s[2].erase(s[2].begin());
            solve(pos+1,2);
            s[2].insert(b);
            ans[pos]=a;
            s[1].erase(s[1].begin());
            solve(pos+1,1);
            s[1].insert(a);
        }
    }
}

signed main(){
    fastio()
    cin >> n;
    for(int i=1;i<=n;i++){
        int t,x;
        cin >> t >> x;
        s[t].insert(x);
    }
    // for(int i=1;i<=8;i++){
    //     cout << i << " -> ";
    //     for(int e:s[i])
    //         cout << e << sp;
    //     cout << nl;
    // }
    if(s[6].empty()){
        ans[1]=*s[5].begin();
        s[5].erase(s[5].begin());
        solve(2,5);
    }
    else{
        ans[1]=*s[6].begin();
        s[6].erase(s[6].begin());
        solve(2,6);        
    }
    cout << -1 << nl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13736 KB Output is correct
2 Correct 80 ms 13764 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13196 KB Output is correct
2 Correct 69 ms 12948 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10436 KB Output is correct
2 Execution timed out 1082 ms 12596 KB Time limit exceeded

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9028 KB Output is correct
2 Correct 54 ms 12996 KB Output is correct
3 Execution timed out 1087 ms 12312 KB Time limit exceeded

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 9536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13192 KB Output is correct
2 Correct 60 ms 9600 KB Output is correct
3 Execution timed out 1100 ms 11868 KB Time limit exceeded

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 12612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15548 KB Output is correct
2 Execution timed out 1087 ms 12612 KB Time limit exceeded

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13024 KB Output is correct
2 Execution timed out 1088 ms 12876 KB Time limit exceeded

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15420 KB Output is correct
2 Execution timed out 1085 ms 14004 KB Time limit exceeded

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 12868 KB Output is correct
2 Execution timed out 1077 ms 12904 KB Time limit exceeded

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13084 KB Output is correct
2 Execution timed out 1095 ms 13480 KB Time limit exceeded