oj.uz

Submission #750145

# Submission time Handle Problem Language Result Execution time Memory
750145 2023-05-29T07:09:57 Z vqpahmad Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 421 ms 104284 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7;
const int N = 1e6 + 15;
const ll inf = 1e18;

int n,k;
vector<pii> ans;
int cnt = 0;
void pr(int o){
    if (k>0&&o>0){
        k--;
        pr(o-1);
        pr(o-1);
        return ;
    }
    cnt++;
    cout << o << ' ';
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> k;
    stack<int> st;
    vector<int> a(n);
    map<int,vector<int>> mp;
    for (int i=0;i<n;i++){
        int x;
        cin >> x;
        a[i] = x;
        if (!i){
            st.push(x);
            continue;
        }
        while (x > st.top()){
            int u = st.top();
            mp[i-1].pb(u);
            while (sz(st)&&u==st.top()){
                st.pop();
                u++;
            }
            st.push(u);
        }
        while (sz(st)&&x==st.top()){
            st.pop();
            x++;
        } 
        st.push(x);
    }
    while (st.top()<30){
        int u = st.top();
        mp[n-1].pb(u);
        while (sz(st)&&u==st.top()){
            st.pop();
            u++;
        }
        st.push(u);
    }
    for (int i=0;i<n;i++){
        ans.push_back({a[i],0});
        for (auto it : mp[i]) {
            ans.push_back({it,1});
            k--;
        }
    }
    while (sz(st)) st.pop();
    n = sz(ans);
    st.push(ans[0].F);
    for (int i=1;i<n;i++){
        int u = ans[i].F;
        while (st.size()&&u==st.top()){
            st.pop();
            u++;
        }
        st.push(u);
    }
    assert(st.top() == 30 && st.size()==1);
    for (int i=0;i<n;i++){
        if (ans[i].S==0){
            cout << ans[i].F << ' ';
        }
        else pr(ans[i].F);
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 104144 KB Output is correct
2 Correct 395 ms 104256 KB Output is correct
3 Correct 401 ms 104284 KB Output is correct
4 Correct 421 ms 104112 KB Output is correct
5 Correct 394 ms 104076 KB Output is correct
6 Correct 404 ms 104052 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 104212 KB Output is correct
2 Correct 332 ms 104132 KB Output is correct
3 Correct 334 ms 104124 KB Output is correct
4 Correct 403 ms 104084 KB Output is correct
5 Correct 398 ms 104212 KB Output is correct
6 Correct 396 ms 104188 KB Output is correct
7 Correct 389 ms 104156 KB Output is correct
8 Correct 405 ms 104112 KB Output is correct
9 Correct 300 ms 89288 KB Output is correct
10 Correct 159 ms 37672 KB Output is correct
11 Correct 211 ms 59460 KB Output is correct
12 Correct 70 ms 2252 KB Output is correct
13 Correct 73 ms 2344 KB Output is correct
14 Correct 74 ms 2300 KB Output is correct