oj.uz

Submission #163683

# Submission time Handle Problem Language Result Execution time Memory
163683 2019-11-14T14:50:12 Z Nashik Zalmoxis (BOI18_zalmoxis) C++14
65 / 100
 457 ms 13740 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 10412 KB Output is correct
2 Correct 378 ms 10308 KB Output is correct
3 Correct 376 ms 10568 KB Output is correct
4 Correct 381 ms 10356 KB Output is correct
5 Correct 379 ms 10332 KB Output is correct
6 Correct 372 ms 10448 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 10224 KB Output is correct
2 Incorrect 375 ms 12796 KB not a zalsequence
3 Incorrect 379 ms 13740 KB not a zalsequence
4 Correct 374 ms 10400 KB Output is correct
5 Correct 417 ms 10236 KB Output is correct
6 Correct 457 ms 10260 KB Output is correct
7 Correct 376 ms 10396 KB Output is correct
8 Correct 394 ms 10360 KB Output is correct
9 Incorrect 351 ms 12816 KB not a zalsequence
10 Incorrect 187 ms 6904 KB not a zalsequence
11 Incorrect 245 ms 9464 KB not a zalsequence
12 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
13 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
14 Correct 95 ms 2396 KB Output is correct