oj.uz

Submission #74048

# Submission time Handle Problem Language Result Execution time Memory
74048 2018-08-29T16:42:05 Z vex Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 1000 ms 16340 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<d;j++)cout<<sol[i]-mmm-1<<" ";
                for(int j=d;j<sd;j++)cout<<sol[i]-mmm<<" ";
            }
            else for(int j=0;j<(1<<sol[i]);j++)cout<<"0"<<" ";
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 15296 KB Output is correct
2 Correct 222 ms 15296 KB Output is correct
3 Correct 322 ms 15352 KB Output is correct
4 Correct 250 ms 15592 KB Output is correct
5 Correct 220 ms 15612 KB Output is correct
6 Correct 245 ms 15612 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 15612 KB Time limit exceeded
2 Execution timed out 1067 ms 15612 KB Time limit exceeded
3 Execution timed out 1083 ms 15612 KB Time limit exceeded
4 Execution timed out 1085 ms 15612 KB Time limit exceeded
5 Execution timed out 1092 ms 15612 KB Time limit exceeded
6 Execution timed out 1088 ms 15612 KB Time limit exceeded
7 Execution timed out 1089 ms 15612 KB Time limit exceeded
8 Execution timed out 1073 ms 15612 KB Time limit exceeded
9 Execution timed out 1083 ms 16340 KB Time limit exceeded
10 Incorrect 189 ms 16340 KB Expected EOF
11 Incorrect 177 ms 16340 KB Expected EOF
12 Incorrect 221 ms 16340 KB Expected EOF
13 Incorrect 198 ms 16340 KB Expected EOF
14 Incorrect 225 ms 16340 KB Expected EOF