oj.uz

Submission #495905

# Submission time Handle Problem Language Result Execution time Memory
495905 2021-12-20T07:39:58 Z AlperenT Slagalica (COCI19_slagalica2) C++17
5 / 70
 26 ms 3052 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

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

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 ? max(cnt[2], cnt[3]) == 0 : true);
    if(a == 'B' && b == 'A') return cnt[1] == cnt[4] && (cnt[1] == 0 ? max(cnt[2], 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';
        else if(x == 6) frst = 'B';

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

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

    if(frst == 'A') ans.push_back(pieces[5].front());
    else ans.push_back(pieces[6].front());

    prv = frst;

    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){
        if(lst == 'A') ans.push_back(pieces[7].front());
        else ans.push_back(pieces[8].front());
    }

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

Compilation message

slagalica.cpp: In function 'int main()':
slagalica.cpp:101:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if(ans.size() == n - 1){
      |        ~~~~~~~~~~~^~~~~~~~
slagalica.cpp:106:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     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 208 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1996 KB Output is correct
2 Incorrect 22 ms 1960 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1780 KB Output is correct
2 Incorrect 18 ms 1844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1856 KB Output is correct
2 Incorrect 19 ms 2280 KB Output isn't correct

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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