oj.uz

Submission #74010

# Submission time Handle Problem Language Result Execution time Memory
74010 2018-08-29T15:35:19 Z vex Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 693 ms 42984 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 265 ms 14268 KB Output is correct
2 Correct 221 ms 14456 KB Output is correct
3 Correct 258 ms 14456 KB Output is correct
4 Correct 214 ms 14572 KB Output is correct
5 Correct 192 ms 14572 KB Output is correct
6 Correct 206 ms 14572 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 389 ms 29496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 510 ms 34200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 401 ms 34240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 533 ms 34240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 430 ms 34240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 481 ms 34240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 430 ms 34240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 441 ms 34240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 693 ms 42984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 128 ms 42984 KB not a zalsequence
11 Incorrect 175 ms 42984 KB doesn't contain S as a subsequence
12 Runtime error 16 ms 42984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 9 ms 42984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 9 ms 42984 KB Execution killed with signal 11 (could be triggered by violating memory limits)