oj.uz

Submission #495919

# Submission time Handle Problem Language Result Execution time Memory
495919 2021-12-20T07:52:58 Z AlperenT Slagalica (COCI19_slagalica2) C++17
70 / 70
 39 ms 2244 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 1 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 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2108 KB Output is correct
2 Correct 31 ms 1884 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1828 KB Output is correct
2 Correct 19 ms 1852 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 844 KB Output is correct
2 Correct 28 ms 1980 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 34 ms 1876 KB Output is correct
3 Correct 34 ms 2172 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1988 KB Output is correct
2 Correct 18 ms 840 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1996 KB Output is correct
2 Correct 23 ms 788 KB Output is correct
3 Correct 29 ms 2080 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1040 KB Output is correct
2 Correct 32 ms 1860 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2244 KB Output is correct
2 Correct 20 ms 1692 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1888 KB Output is correct
2 Correct 19 ms 1808 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2232 KB Output is correct
2 Correct 29 ms 1912 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1956 KB Output is correct
2 Correct 19 ms 1836 KB Output is correct

Subtask #14
5.0 / 5.0

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