Submission #589322

#	Time	Username	Problem	Language	Result	Execution time	Memory
589322		MasterTaster	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	234 ms	34036 KiB

zalmoxis

#include<iostream>
#include<stack>
#include<vector>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 1000010

using namespace std;

int n, k, a[MAXN];
vector<int> dodao[MAXN];
stack<int> st;


void deli (int x)
{
    if (x==0) { cout<<x<<" "; return; }
    k--;
    if (k>0) { deli(x-1); if (k>0) deli(x-1); else cout<<x-1<<" "; }
    else cout<<x-1<<" "<<x-1<<" ";
}
void ispisi()
{
    stack<int> st1=st;
    while (!st1.empty()) { cout<<st1.top()<<" "; st1.pop(); }
    cout<<endl;
}

int main() {
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>a[i];
    a[n+1]=30;

    for (int i=1; i<=n+1; i++)
    {
        if (st.empty() || a[i]<st.top()) st.push(a[i]);
        else if (a[i]==st.top())
        {
            int sta=a[i];
            while (!st.empty() && sta==st.top())
            {
                st.pop(); sta++;
            }
            st.push(sta);
        }
        else
        {
            while (st.top()<a[i])
            {
                int sta=st.top(); dodao[i].pb(sta);
                while (!st.empty() && sta==st.top()) {
                    st.pop();
                    sta++;
                }
                st.push(sta);
            }
            int sta=a[i];
            while (!st.empty() && sta==st.top())
            {
                st.pop(); sta++;
            }
            st.push(sta);
        }
        /*cout<<i<<":"<<endl;
        ispisi();
        cout<<"A dodao sam: "<<endl;
        for (auto x:dodao[i]) cout<<x<<" ";
        if (dodao[i].size()) cout<<endl;*/
    }

    /*while (!st.empty() && st.top()!=30) {
        dodao[n + 1].pb(st.top());
        st.top()++;
    }*/

    for (int i=1; i<=n+1; i++) k-=dodao[i].size();
    for (int i=1; i<=n+1; i++)
    {
        for (auto x:dodao[i])
        {
            if (k>0) deli(x);
            else cout<<x<<" ";
        }
        if (i<=n) cout<<a[i]<<" ";
    }
}

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