Submission #668201

#	Time	Username	Problem	Language	Result	Execution time	Memory
668201		1zaid1	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	564 ms	96412 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int M = 3e5+10;

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, k;
    cin >> n >> k;

    vector<int> v(n), v1;
    for (int &i:v) cin >> i;
    vector<int> x;
for (int i:v) x.push_back(i);

    map<int, int> vis;
    reverse(v.begin(), v.end());
    vector<int> st; st.push_back(v.back());

    v1 = {v.back()};
    v.pop_back();
    while (st.back() != 30) {
        if (v.empty()) {
            for (int i = st.back(); i < 30; i++) {
                vis[v1.size()] = true;
                v1.push_back(i);
            }

            break;
        } else {
            int h = v.back();
            int w = st.back();

            if (h == w) {
                v1.push_back(h);
                v.pop_back();
                while (st.size() && h == w) {
                    h = w+1;
                    st.pop_back();
                    if (st.size()) w = st.back();
                } st.push_back(h);
            } else if (h < w) {
                v.pop_back();
                st.push_back(h);
                v1.push_back(h);
            } else {
                v.push_back(w);
            }
        }
    } swap(v, x);

    int j = 0;
    for (int i = 0; i < v.size(); i++) {
        while (v[i] != v1[j]) {
            vis[j] = 1, j++;
        }

        j++;
    }

    while (j < v1.size()) vis[j++] = true;

    vector<int> ans;
    for (int i = 0; i < v1.size(); i++) {
        ans.push_back(v1[i]);
        k -= vis[i];
        if (vis[i]&&k>0) {
            while (ans.back()>0 && k > 0) {
                k--;
                ans.back()--;
                ans.push_back(ans.back());
            }
        }

        // cout << k << endl;
    }

    // for (int j=0;j<v1.size();j++) cout << vis[j]; cout << endl;
    // for (int i:v) cout << i << ' '; cout << endl;
    // for (int i:v1) cout << i << ' '; cout << endl;
    for (int i:ans) cout << i << ' '; cout << endl;

    return 0;
}

/*
5 1
29 27 25 25 28

1 5
29
*/

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:56:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zalmoxis.cpp:64:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     while (j < v1.size()) vis[j++] = true;
      |            ~~^~~~~~~~~~~
zalmoxis.cpp:67:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < v1.size(); i++) {
      |                     ~~^~~~~~~~~~~
zalmoxis.cpp:84:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   84 |     for (int i:ans) cout << i << ' '; cout << endl;
      |     ^~~
zalmoxis.cpp:84:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |     for (int i:ans) cout << i << ' '; cout << endl;
      |                                       ^~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70