Submission #163683

#	Time	Username	Problem	Language	Result	Execution time	Memory
163683		Nashik	Zalmoxis (BOI18_zalmoxis)	C++14	65 / 100	457 ms	13740 KiB

zalmoxis

#include <iostream>
#include <fstream>
using namespace std;
int n,k,v[1000005],cnt=0;
pair<int,int> st[1000005];
int pls[1000005],cont=0,last=0,sol[1000005],in_plus;
int f[50];
void func(int a){
    if(in_plus==n+k){
        cout<<a<<" ";
        return;
    }
    if(a==0){
        cout<<0<<" ";
        return;
    }
    if(f[a]-1+in_plus<=n+k){
        for(int i=1;i<=f[a];i++){
            cout<<0<<" ";
        }
        in_plus+=f[a]-1;
        return;
    }
    if(f[a]+in_plus<=n+k){
        for(int i=1;i<=f[a];i++){
            cout<<0<<" ";
        }
        in_plus+=f[a]-1;
        func(a-1);
        return;
    }
    in_plus++;
    func(a-1);
    cout<<a-1<<" ";
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    f[0]=1;
    for(int i=1;i<=30;i++){
        f[i]=f[i-1]*2;
    }
    for(int i=1;i<=n;i++){
        //for(int j=1;j<=cnt;j++){
            //cout<<st[j].first<<" "<<st[j].second<<"->";
        //}
        //cout<<"\n\n";
        if(cnt==0){
            st[++cnt]=make_pair(++last,v[i]);
        }
        else{
            while(st[cnt].second<v[i] and cnt!=0){
                pls[++st[cnt].first]=st[cnt].second;
                st[cnt].second++;
                cont++;
                while(cnt>1){
                    if(st[cnt].second==st[cnt-1].second){
                        st[cnt-1].first=st[cnt].first;
                        st[cnt-1].second++;
                        cnt--;
                    }
                    else
                        break;
                }
                last=st[cnt].first;
            }
            st[++cnt]=make_pair(last+1,v[i]);
            while(st[cnt].second==st[cnt-1].second and cnt!=0){
                st[cnt-1].first=st[cnt].first;
                st[cnt-1].second++;
                cnt--;
            }
            last=st[cnt].first;
        }
    }
    //cout<<"ajunge aici\n";
    while(cnt>1){
        pls[++last]=st[cnt].second;
        st[cnt].second++;
        st[cnt].first=last;
        while(cnt>1){
            if(st[cnt].second==st[cnt-1].second){
                st[cnt-1].first=st[cnt].first;
                st[cnt-1].second++;
                cnt--;
            }
            else
                break;
        }
    }
    int fin=st[1].second;
    int lung=st[1].first;
    //cout<<fin<<" "<<lung<<"\n";
    while(fin<30){
        pls[++lung]=fin;
        fin++;
    }
    //cout<<"\n";
    //for(int i=1;i<=lung;i++){
        //cout<<pls[i]<<" ";
    //}
    //cout<<"\n";
    for(int i=1;i<=n;i++){
        while(pls[cnt]!=0){
            sol[cnt]=pls[cnt];
            cnt++;
        }
        sol[cnt]=v[i];
        cnt++;
    }
    while(pls[cnt]!=0){
        sol[cnt]=pls[cnt];
        cnt++;
    }
    cnt--;
    //cout<<"\n\n";
    in_plus=cnt;
    //cout<<cnt<<"\n\n";
    for(int i=1;i<=cnt;i++){
        //cout<<"--"<<in_plus<<"--";
        if(pls[i]==0)
            cout<<sol[i]<<" ";
        else{
            if(in_plus==n+k){
                cout<<sol[i]<<" ";
            }
            else{
                func(sol[i]);
            }
        }
    }
    //cout<<in_plus<<"\n";
    return 0;
}
/**
4
3 3
2 2 3
1 1 1 1 3


4
3 3
2 2 2 2
1 1 1 1 1 1 1 1

29 29
29 28 28
29 28 27 27


3 4
29 28 28
*/

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