oj.uz

Submission #634212

# Submission time Handle Problem Language Result Execution time Memory
634212 2022-08-24T06:03:58 Z HaYoungJoon Slagalica (COCI19_slagalica2) C++14
35 / 70
 43 ms 2216 KB 
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef pair<int,int> pii;
pii change[9];
int n, cnt[5];
vector<int> type[9];

void makeChange() {
    change[1] = pii(1,3);
    change[2] = pii(1,4);
    change[3] = pii(2,3);
    change[4] = pii(2,4);
    change[5] = pii(0,3);
    change[6] = pii(0,4);
    change[7] = pii(1,0);
    change[8] = pii(2,0);
}

bool checkChoose(int t) {
    int cnt1 = cnt[1] ;
    int cnt2 = cnt[2] ;
    int cnt3 = cnt[3] + (change[t].se == 3);
    int cnt4 = cnt[4] + (change[t].se == 4);
    return (cnt1 == cnt4 && cnt2 == cnt3);
}
bool cmp(int A, int B) {return A > B;}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    makeChange();
    for (int i = 1; i <= n; i++) {
        int t,id;
        cin >> t >> id;
        type[t].push_back(id);
        if (t < 5) {
            cnt[change[t].fi]++;
            cnt[change[t].se]++;
        }
    }
    for (int i = 1; i <= 4; i++) sort(type[i].begin(),type[i].end(),cmp);
    int st = (type[5].empty()) ? 6: 5;
    int fin = (type[7].empty()) ? 8: 7;
    if (fin == 7) cnt[1]++;
    else cnt[2]++;
    if (st == 5) cnt[3]++;
    else cnt[4]++;
    vector<int> res;
    if (cnt[1] != cnt[4] || cnt[2] != cnt[3]) {
        cout << -1;
        return 0;
    }
    if (st == 5) cnt[3]--;
    else cnt[4]--;
    res.push_back(type[st].back());
    int pre = (st == 5) ? 3: 4;
    while (res.size() < n-1) {
        int t;
        if (pre == 3) {
            if (type[3].empty()) t = 4;
            else if (type[4].empty()) t = 3;
            else if (!checkChoose(3) && !checkChoose(4)) assert(0);
            else if (!checkChoose(4)) t = 3;
            else if (!checkChoose(3)) t = 4;
            else t = (type[3].back() < type[4].back()) ? 3 : 4;
        } else {
            if (type[1].empty()) t = 2;
            else if (type[2].empty()) t = 1;
            else if (!checkChoose(1) && !checkChoose(2)) assert(0);
            else if (!checkChoose(2)) t = 1;
            else if (!checkChoose(1)) t = 2;
            else t = (type[1].back() < type[2].back()) ? 1 : 2;
        }
        res.push_back(type[t].back());
        type[t].pop_back();
        cnt[change[t].fi]--;
        cnt[change[t].se]--;
        pre = change[t].se;
    }
    res.push_back(type[fin].back());
    for (int i: res) cout << i << ' ';
    return 0;
}

Compilation message

slagalica.cpp: In function 'int main()':
slagalica.cpp:62:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     while (res.size() < n-1) {
      |            ~~~~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2032 KB Output is correct
2 Correct 22 ms 852 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 860 KB Output is correct
2 Correct 39 ms 1988 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 784 KB Output is correct
2 Correct 37 ms 1864 KB Output is correct
3 Correct 42 ms 2120 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1884 KB Output is correct
2 Correct 23 ms 868 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1912 KB Output is correct
2 Correct 24 ms 892 KB Output is correct
3 Correct 42 ms 2052 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 968 KB Output is correct
2 Incorrect 28 ms 1956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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