Submission #1293664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293664		Hamed_Ghaffari	Zalmoxis (BOI18_zalmoxis)	C++20	100 / 100	91 ms	14316 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) int(x.size())

const int MXN = 1e6+5;

int n, k, a[MXN];

vector<int> solve(int add) {
    vector<int> L, R;
    L.push_back(30);
    int ptr=1;
    while(ptr<=n) {
        if(L.back()<a[ptr]) {
            if(L.back() && add) {
                L.back()--;
                R.push_back(L.back());
                add--;
            }
            else {
                L.push_back(R.back());
                R.pop_back();
            }
        }
        else if(L.back()>a[ptr]) {
            L.back()--;
            R.push_back(L.back());
        }
        else {
            if(ptr+1<=n) {
                L.push_back(R.back());
                R.pop_back();
            }
            ptr++;
        }
    }
    while(!R.empty()) {
        L.push_back(R.back());
        R.pop_back();
        while(L.back() && add) {
            L.back()--;
            R.push_back(L.back());
            add--;
        }
    }
    return L;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    vector<int> ans = solve(n+k-SZ(solve(0)));
    for(int i : ans)
        cout << i << ' ';
    cout << '\n';
    return 0;
}

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