oj.uz

Submission #657752

# Submission time Handle Problem Language Result Execution time Memory
657752 2022-11-11T00:07:46 Z Danilo21 Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 174 ms 20488 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m;
vector<int> a;

void Print(stack<int> s){

    while (s.size()){
        cout << s.top() << sp;
        s.pop();
    }
    cout << en;
}

void Add(int x){

    if (!x || !m){
        a.pb(x);
        return;
    }
    m--;
    Add(x-1); Add(x-1);
}

void Insert(int x, stack<int>& stk){

    while (stk.size() && stk.top() == x){ stk.pop(); x++; }
    stk.push(x);
}

void Solve(){

    cin >> n >> m;
    vector<array<int, 2> > ans;
    stack<int> stk;
    for (int i = 0; i <= n; i++){
        int x;
        if (i < n) cin >> x;
        else x = 30;
        while (stk.size() && stk.top() < x){
            int t = stk.top(); stk.pop();
            ans.pb({t, 1}); m--;
            Insert(t+1, stk);
        }
        if (i < n) ans.pb({x, 0});
        Insert(x, stk);
    }
    for (auto [x, t] : ans){
        if (t) Add(x);
        else a.pb(x);
    }
    pv(a);
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 20268 KB Output is correct
2 Correct 141 ms 20236 KB Output is correct
3 Correct 145 ms 20340 KB Output is correct
4 Correct 142 ms 20240 KB Output is correct
5 Correct 147 ms 20488 KB Output is correct
6 Correct 138 ms 20152 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 20204 KB Output is correct
2 Correct 142 ms 20236 KB Output is correct
3 Correct 138 ms 20212 KB Output is correct
4 Correct 145 ms 20256 KB Output is correct
5 Correct 149 ms 20344 KB Output is correct
6 Correct 137 ms 20240 KB Output is correct
7 Correct 139 ms 20292 KB Output is correct
8 Correct 145 ms 20396 KB Output is correct
9 Correct 133 ms 19328 KB Output is correct
10 Correct 92 ms 10432 KB Output is correct
11 Correct 123 ms 16556 KB Output is correct
12 Correct 72 ms 6404 KB Output is correct
13 Correct 71 ms 6284 KB Output is correct
14 Correct 72 ms 6284 KB Output is correct