oj.uz

Submission #495913

# Submission time Handle Problem Language Result Execution time Memory
495913 2021-12-20T07:49:19 Z AlperenT Slagalica (COCI19_slagalica2) C++17
25 / 70
 50 ms 3248 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, x, a, cnt[10], frstx, lstx;

vector<int> pieces[10], ans;

char prv, frst, lst;

bool check(char a, char b){
    if(a == 'A' && b == 'A') return cnt[1] + 1 == cnt[4];
    if(a == 'A' && b == 'B') return cnt[1] == cnt[4] && (cnt[1] == 0 ? cnt[2] == 0 : true);
    if(a == 'B' && b == 'A') return cnt[1] == cnt[4] && (cnt[1] == 0 ? cnt[3] == 0 : true);
    if(a == 'B' && b == 'B') return cnt[1] == cnt[4] + 1;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> x >> a;

        pieces[x].push_back(a);
        cnt[x]++;

        if(x == 5) frst = 'A', frstx = 5;
        else if(x == 6) frst = 'B', frstx = 6;

        if(x == 7) lst = 'A', lstx = 7;
        else if(x == 8) lst = 'B', lstx = 8;
    }

    for(int i = 1; i < 4; i++) sort(pieces[i].begin(), pieces[i].end(), greater<int>());

    ans.push_back(pieces[frstx].front());

    prv = frst;

    if(n == 2){
        if(frst != lst) ans.push_back(pieces[lstx].front());
    }
    else{
        for(int i = 2; i <= n - 1; i++){
            int mn = -1;

            if(prv == 'A'){
                if(cnt[3]){
                    cnt[3]--;

                    if(check('A', lst)){
                        if(mn == -1 || pieces[3].back() < pieces[mn].back()) mn = 3;
                    }

                    cnt[3]++;
                }

                if(cnt[4]){
                    cnt[4]--;

                    if(check('B', lst)){
                        if(mn == -1 || pieces[4].back() < pieces[mn].back()) mn = 4;
                    }

                    cnt[4]++;
                }
            }
            else if(prv == 'B'){
                if(cnt[1]){
                    cnt[1]--;

                    if(check('A', lst)){
                        if(mn == -1 || pieces[1].back() < pieces[mn].back()) mn = 1;
                    }

                    cnt[1]++;
                }

                if(cnt[2]){
                    cnt[2]--;

                    if(check('B', lst)){
                        if(mn == -1 || pieces[2].back() < pieces[mn].back()) mn = 2;
                    }

                    cnt[2]++;
                }
            }

            if(mn == -1) break;
            else{
                ans.push_back(pieces[mn].back());
                pieces[mn].pop_back(); cnt[mn]--;

                if(mn == 1 || mn == 3) prv = 'A';
                else prv = 'B';
            }
        }

        if(ans.size() == n - 1) ans.push_back(pieces[lstx].front());
    }

    if(ans.size() == n) for(auto i : ans) cout << i << " ";
    else cout << -1;
}

Compilation message

slagalica.cpp: In function 'int main()':
slagalica.cpp:104:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |         if(ans.size() == n - 1) ans.push_back(pieces[lstx].front());
      |            ~~~~~~~~~~~^~~~~~~~
slagalica.cpp:107:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |     if(ans.size() == n) for(auto i : ans) cout << i << " ";
      |        ~~~~~~~~~~~^~~~
slagalica.cpp: In function 'bool check(char, char)':
slagalica.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 828 KB Output is correct
2 Correct 27 ms 2020 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 760 KB Output is correct
2 Correct 27 ms 1820 KB Output is correct
3 Correct 50 ms 3248 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1852 KB Output is correct
2 Correct 21 ms 1856 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1948 KB Output is correct
2 Correct 21 ms 1864 KB Output is correct
3 Correct 28 ms 3072 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 916 KB Output is correct
2 Incorrect 27 ms 1852 KB Output isn't correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 2264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 2024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2032 KB Output isn't correct
2 Halted 0 ms 0 KB -