oj.uz

Submission #74053

# Submission time Handle Problem Language Result Execution time Memory
74053 2018-08-29T16:47:55 Z vex Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 313 ms 16492 KB 
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;

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

void precalc()
{
    s[0]=0;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+(1<<a[i]);
}

void solve(int l,int r,int x)
{
    if(l>r)
    {
        sol.push_back(x);
        bio[sol.size()-1]=false;
        return;
    }
    if(l==r)
    {
        int is=1<<x;
        sol.push_back(a[l]);
        bio[sol.size()-1]=true;

        is-=1<<a[l];
        int br=0;
        while(is>0)
        {
            if(is%2)
            {
                sol.push_back(br);
                bio[sol.size()-1]=false;
            }
            br++;
            is/=2;
        }
        return;
    }

    int left=l;
    int right=r;
    int br=1<<(x-1);
    int t=l;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(s[mid]-s[l-1]>br)right=mid-1;
        else {
           t=mid;
           left=mid+1;
        }
    }

    solve(l,t,x-1);
    solve(t+1,r,x-1);
}

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

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

    precalc();
    solve(1,n,30);

    int sz=sol.size();
    int d=n+k-sz;
    int mmm=30;

    for(int i=0;i<sz;i++)
    {
        if(d<=0 || bio[i])cout<<sol[i]<<" ";
        else{
            while((1<<mmm)-1>d)mmm--;
            if((1<<sol[i])-1>d)
            {
                int sd=d;
                d-=1<<mmm;
                d++;
                for(int j=0;j<2*d;j++)cout<<sol[i]-mmm-1<<" ";
                for(int j=2*d;j<sd+1;j++)cout<<sol[i]-mmm<<" ";
                
            }
            else {
                for(int j=0;j<(1<<sol[i]);j++)cout<<"0 ";
                d-=1<<sol[i];
                d++;
            }
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 15200 KB Output is correct
2 Correct 203 ms 15324 KB Output is correct
3 Correct 208 ms 15440 KB Output is correct
4 Correct 193 ms 15440 KB Output is correct
5 Correct 199 ms 15516 KB Output is correct
6 Correct 288 ms 15540 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 15540 KB Expected EOF
2 Incorrect 206 ms 15856 KB Expected EOF
3 Incorrect 215 ms 15856 KB Expected EOF
4 Incorrect 199 ms 15856 KB Expected EOF
5 Incorrect 307 ms 15856 KB Expected EOF
6 Incorrect 226 ms 15856 KB Expected EOF
7 Incorrect 313 ms 15856 KB Expected EOF
8 Incorrect 252 ms 15856 KB Expected EOF
9 Incorrect 223 ms 16492 KB Expected EOF
10 Incorrect 116 ms 16492 KB Expected EOF
11 Incorrect 166 ms 16492 KB Expected EOF
12 Incorrect 79 ms 16492 KB Expected EOF
13 Incorrect 73 ms 16492 KB Expected EOF
14 Incorrect 86 ms 16492 KB Expected EOF