Submission #59787

#	Time	Username	Problem	Language	Result	Execution time	Memory
59787		model_code	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	332 ms	18492 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1000000 + 5;

int N, K;
int v[NMAX];

pair <int, bool> ans[NMAX];
int ansSz;
int stk[NMAX], stkSz;

inline void pushAns(int val, bool type) {
    ans[++ ansSz] = make_pair(val, type), K -= type;
}

inline void pushStk(int val) { stk[++ stkSz] = val; }
inline void popStk() { -- stkSz; }

inline void compressStk() {
   while (stkSz >= 2 && stk[stkSz] == stk[stkSz - 1])
        popStk(), ++ stk[stkSz];
}
inline void addAndCompressToStk() {
    pushAns(stk[stkSz], true);
    ++ stk[stkSz];
    compressStk();
}

int res[NMAX], resSz;
void doPrint(int nr) {
    if (K == 0 || nr == 0)
        res[++ resSz] = nr;
    else
        -- K, doPrint(nr - 1), doPrint(nr - 1);
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin >> N >> K;
    for (int i = 1; i <= N; ++ i)
        cin >> v[i];
    
    // Process string
    pushStk(31); // Sentinel
    for (int i = 1; i <= N; ++ i) {
        while (v[i] > stk[stkSz])
            addAndCompressToStk();
        pushAns(v[i], false), pushStk(v[i]);
        compressStk();
    }
    
    // Finalize
    while (stk[2] != 30)
        addAndCompressToStk();
    
    // Expand elements, if necessary
    for (int i = 1; i <= ansSz; ++ i) {
         if (ans[i].second == false)
            res[++ resSz] = ans[i].first;
        else
            doPrint(ans[i].first);
    }

    // Print solution
    for (int i = 1; i <= resSz; ++ i)
        cout << res[i] << " \n"[i == resSz];
    return 0;
}

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