oj.uz

Submission #650780

# Submission time Handle Problem Language Result Execution time Memory
650780 2022-10-15T10:50:24 Z Matteo_Verz Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 159 ms 16432 KB 
#include <bits/stdc++.h>
#ifdef BLAT
    #include "debug/debug.hpp"
#else
    #define debug(x...)
#endif

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() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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:64: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]
   64 |     for (int i = 0; i < finalv.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 16280 KB Output is correct
2 Correct 136 ms 16340 KB Output is correct
3 Correct 142 ms 16352 KB Output is correct
4 Correct 132 ms 16356 KB Output is correct
5 Correct 143 ms 16308 KB Output is correct
6 Correct 134 ms 16212 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 16352 KB Output is correct
2 Correct 159 ms 16328 KB Output is correct
3 Correct 142 ms 16304 KB Output is correct
4 Correct 133 ms 16340 KB Output is correct
5 Correct 139 ms 16348 KB Output is correct
6 Correct 135 ms 16432 KB Output is correct
7 Correct 142 ms 16344 KB Output is correct
8 Correct 135 ms 16356 KB Output is correct
9 Correct 136 ms 13344 KB Output is correct
10 Correct 104 ms 7616 KB Output is correct
11 Correct 119 ms 11372 KB Output is correct
12 Correct 85 ms 2272 KB Output is correct
13 Correct 80 ms 2228 KB Output is correct
14 Correct 81 ms 2268 KB Output is correct