oj.uz

Submission #634210

# Submission time Handle Problem Language Result Execution time Memory
634210 2022-08-24T06:03:22 Z HaYoungJoon Slagalica (COCI19_slagalica2) C++14
35 / 70
 35 ms 3400 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()) ? 4 : 3;
        } 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()) ? 2 : 1;
        }
        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 0 ms 212 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 1 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 34 ms 3020 KB Output is correct
2 Correct 23 ms 1896 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2912 KB Output is correct
2 Correct 21 ms 1780 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2052 KB Output is correct
2 Correct 30 ms 3032 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1824 KB Output is correct
2 Correct 31 ms 2892 KB Output is correct
3 Correct 35 ms 3244 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2908 KB Output is correct
2 Correct 23 ms 1872 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2860 KB Output is correct
2 Correct 21 ms 1892 KB Output is correct
3 Correct 31 ms 3204 KB Output is correct

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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