oj.uz

Submission #59787

# Submission time Handle Problem Language Result Execution time Memory
59787 2018-07-23T06:12:36 Z model_code Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 332 ms 18492 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 18168 KB Output is correct
2 Correct 247 ms 18284 KB Output is correct
3 Correct 257 ms 18384 KB Output is correct
4 Correct 248 ms 18432 KB Output is correct
5 Correct 204 ms 18432 KB Output is correct
6 Correct 187 ms 18432 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 18432 KB Output is correct
2 Correct 247 ms 18432 KB Output is correct
3 Correct 277 ms 18432 KB Output is correct
4 Correct 222 ms 18432 KB Output is correct
5 Correct 204 ms 18492 KB Output is correct
6 Correct 218 ms 18492 KB Output is correct
7 Correct 332 ms 18492 KB Output is correct
8 Correct 187 ms 18492 KB Output is correct
9 Correct 222 ms 18492 KB Output is correct
10 Correct 189 ms 18492 KB Output is correct
11 Correct 244 ms 18492 KB Output is correct
12 Correct 164 ms 18492 KB Output is correct
13 Correct 98 ms 18492 KB Output is correct
14 Correct 95 ms 18492 KB Output is correct