oj.uz

Submission #589322

# Submission time Handle Problem Language Result Execution time Memory
589322 2022-07-04T12:57:16 Z MasterTaster Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 234 ms 34036 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 31780 KB Output is correct
2 Correct 228 ms 31820 KB Output is correct
3 Correct 223 ms 31792 KB Output is correct
4 Correct 224 ms 31836 KB Output is correct
5 Correct 223 ms 31820 KB Output is correct
6 Correct 221 ms 31692 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 31936 KB Output is correct
2 Correct 220 ms 31848 KB Output is correct
3 Correct 226 ms 31820 KB Output is correct
4 Correct 228 ms 31796 KB Output is correct
5 Correct 233 ms 31820 KB Output is correct
6 Correct 234 ms 31804 KB Output is correct
7 Correct 221 ms 31824 KB Output is correct
8 Correct 223 ms 31856 KB Output is correct
9 Correct 216 ms 34036 KB Output is correct
10 Correct 145 ms 30284 KB Output is correct
11 Correct 179 ms 32324 KB Output is correct
12 Correct 101 ms 25804 KB Output is correct
13 Correct 94 ms 25692 KB Output is correct
14 Correct 97 ms 25676 KB Output is correct