Submission #495919

#	Time	Username	Problem	Language	Result	Execution time	Memory
495919		AlperenT	Slagalica (COCI19_slagalica2)	C++17	70 / 70	39 ms	2244 KiB

slagalica

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

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