oj.uz

Submission #74434

# Submission time Handle Problem Language Result Execution time Memory
74434 2018-09-01T09:50:33 Z vex Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 185 ms 11660 KB 
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;

int n,k;
int a[maxn];
vector<int>sol;
stack<int>s;
bool nov[maxn];

void solve()
{
    s.push(a[0]);
    
    sol.push_back(a[0]);
    nov[0]=false;

    for(int i=1;i<n;i++)
    {
        while(!s.empty() && s.top()<a[i])
        {
            sol.push_back(s.top());
            nov[sol.size()-1]=true;

            int tt=s.top()+1;s.pop();
            while(!s.empty() && s.top()==tt)
            {
                s.pop();
                tt++;
            }
            s.push(tt);
        }

        if(s.top()==a[i])
        {
            sol.push_back(a[i]);
            nov[sol.size()-1]=false;
            
            s.pop();

            int tt=a[i]+1;
            while(!s.empty() && s.top()==tt)
            {
                s.pop();
                tt++;
            }
            s.push(tt);
        }
        else{
            s.push(a[i]);
            
            sol.push_back(a[i]);
            nov[sol.size()-1]=false;
        }
    }

    while(s.top()!=30)
    {
        sol.push_back(s.top());
        nov[sol.size()-1]=true;
        
        int tt=s.top()+1;
        s.pop();

        while(!s.empty() && s.top()==tt)
        {
            s.pop();
            tt++;
        }
        s.push(tt);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];

    solve();
    //for(auto x:sol)cout<<x<<" ";

    int sz=sol.size();
    k-=(sz-n);
    int mmm=30;
    for(int i=0;i<sz;i++)
    {
        if(!nov[i] || k==0)cout<<sol[i]<<" ";
        else if((1<<sol[i])-1 >=k)
        {
            while((1<<mmm) > k)mmm--;
            int ost=k-(1<<mmm)+1;
            for(int j=0;j<2*ost;j++)cout<<sol[i]-mmm-1<<" ";
            for(int j=2*ost;j<=k;j++)cout<<sol[i]-mmm<<" ";
            k=0;
        }
        else
        {
            for(int j=0;j<(1<<sol[i]);j++)cout<<"0 ";
            k-=(1<<sol[i]);
            k++;
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 11360 KB Output is correct
2 Correct 165 ms 11496 KB Output is correct
3 Correct 171 ms 11528 KB Output is correct
4 Correct 168 ms 11640 KB Output is correct
5 Correct 177 ms 11640 KB Output is correct
6 Correct 165 ms 11640 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 11640 KB Output is correct
2 Correct 179 ms 11660 KB Output is correct
3 Correct 167 ms 11660 KB Output is correct
4 Correct 172 ms 11660 KB Output is correct
5 Correct 171 ms 11660 KB Output is correct
6 Correct 165 ms 11660 KB Output is correct
7 Correct 166 ms 11660 KB Output is correct
8 Correct 166 ms 11660 KB Output is correct
9 Correct 152 ms 11660 KB Output is correct
10 Correct 94 ms 11660 KB Output is correct
11 Correct 122 ms 11660 KB Output is correct
12 Correct 54 ms 11660 KB Output is correct
13 Correct 52 ms 11660 KB Output is correct
14 Correct 53 ms 11660 KB Output is correct