oj.uz

Submission #74008

# Submission time Handle Problem Language Result Execution time Memory
74008 2018-08-29T15:32:06 Z vex Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 840 ms 45092 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 najv2(int x)
{
    int l=0;
    int r=30;
    int sss=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int br=(1<<mid)-1;
        if(br>x)r=mid-1;
        else{
            sss=mid;
            l=mid+1;
        }
    }
    return sss;
}

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;

    for(int i=0;i<sz;i++)
    {
        if(d==0 || bio[i])cout<<sol[i]<<" ";
        else{
            int mmm=najv2(d);
            int minn=min(mmm,sol[i]);
            for(int i=1;i<=(1<<minn);i++)cout<<sol[i]-minn<<" ";
            d-=1<<minn;
            d++;
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 15328 KB Output is correct
2 Correct 226 ms 15328 KB Output is correct
3 Correct 233 ms 15448 KB Output is correct
4 Correct 201 ms 15448 KB Output is correct
5 Correct 243 ms 15648 KB Output is correct
6 Correct 234 ms 15648 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 ms 31240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 475 ms 36080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 489 ms 36100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 492 ms 36124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 449 ms 36124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 470 ms 36124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 492 ms 36124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 455 ms 36124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 840 ms 45092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 200 ms 45092 KB not a zalsequence
11 Incorrect 180 ms 45092 KB not a zalsequence
12 Runtime error 10 ms 45092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 8 ms 45092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 10 ms 45092 KB Execution killed with signal 11 (could be triggered by violating memory limits)