oj.uz

Submission #650593

# Submission time Handle Problem Language Result Execution time Memory
650593 2022-10-14T08:57:52 Z Matteo_Verz Zalmoxis (BOI18_zalmoxis) C++17
15 / 100
 1000 ms 8120 KB 
#include <bits/stdc++.h>

using namespace std;

bool removeElements(vector <int> &st) {
    bool removed = false;
    while (st.size() > 1 && st[st.size() - 1] == st[st.size() - 2]) {
        removed = true;
        st.pop_back();
        st.back()++;
    }

    return removed;
}

void print(int n, int &k) {
    if (n == 0 || k == 0) cout << n << ' ';
    else {
        k--;
        print(n - 1, k);
        print(n - 1, k);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    vector <int> v(1 + n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    v[n] = 30;

    vector <pair <int, bool>> finalv;
    vector <int> st;
    for (int i = 0; i <= n; i++) {
        cerr << "st: ";
        for (auto it : st)
            cerr << it << ' ';
        cerr << '\n';
        if (st.size() && v[i] > st.back()) {
            while (v[i] > st.back()) {
                finalv.push_back(make_pair(st.back(), 1));
                k--;
                st.back()++;
                removeElements(st);
            }
        } 
        if (st.size() && v[i] == st.back()) {
            st.back()++;
            removeElements(st);
        } else st.push_back(v[i]);

        removeElements(st);
        finalv.push_back(make_pair(v[i], 0));
    }

    for (int i = 0; i < finalv.size() - 1; i++) {
        if (finalv[i].second == 1) print(finalv[i].first, k);
        else cout << finalv[i].first << ' ';
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < finalv.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 7932 KB Time limit exceeded
2 Execution timed out 1045 ms 7988 KB Time limit exceeded
3 Execution timed out 1087 ms 8076 KB Time limit exceeded
4 Execution timed out 1061 ms 8048 KB Time limit exceeded
5 Execution timed out 1071 ms 7892 KB Time limit exceeded
6 Execution timed out 1094 ms 7908 KB Time limit exceeded

Subtask #2
15.0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 8120 KB Time limit exceeded
2 Execution timed out 1091 ms 7924 KB Time limit exceeded
3 Execution timed out 1076 ms 8068 KB Time limit exceeded
4 Execution timed out 1082 ms 8060 KB Time limit exceeded
5 Execution timed out 1090 ms 7568 KB Time limit exceeded
6 Execution timed out 1054 ms 7592 KB Time limit exceeded
7 Execution timed out 1096 ms 7900 KB Time limit exceeded
8 Execution timed out 1078 ms 7588 KB Time limit exceeded
9 Execution timed out 1091 ms 5348 KB Time limit exceeded
10 Execution timed out 1067 ms 4036 KB Time limit exceeded
11 Execution timed out 1050 ms 4784 KB Time limit exceeded
12 Correct 92 ms 2304 KB Output is correct
13 Correct 91 ms 2352 KB Output is correct
14 Correct 90 ms 2248 KB Output is correct