Submission #495905

#	Time	Username	Problem	Language	Result	Execution time	Memory
495905		AlperenT	Slagalica (COCI19_slagalica2)	C++17	5 / 70	26 ms	3052 KiB

slagalica

#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 (stderr)

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 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5