oj.uz

Submission #74011

# Submission time Handle Problem Language Result Execution time Memory
74011 2018-08-29T15:38:39 Z vex Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 723 ms 43136 KB 
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
 
int n,k;
int a[maxn];
vector<int>sol;
int s[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);
        return;
    }
    if(l==r)
    {
        int s=1<<x;
        sol.push_back(a[l]);
        s-=1<<a[l];
        int br=0;
        while(s>0)
        {
            if(s%2)sol.push_back(br);
            br++;
            s/=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)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 215 ms 14264 KB Output is correct
2 Correct 211 ms 14408 KB Output is correct
3 Correct 233 ms 14408 KB Output is correct
4 Correct 217 ms 14436 KB Output is correct
5 Correct 227 ms 14436 KB Output is correct
6 Correct 236 ms 14436 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 263 ms 29464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 381 ms 34092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 466 ms 34172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 422 ms 34172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 406 ms 34172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 555 ms 34172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 434 ms 34172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 563 ms 34172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 723 ms 43136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 136 ms 43136 KB not a zalsequence
11 Incorrect 180 ms 43136 KB doesn't contain S as a subsequence
12 Runtime error 11 ms 43136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 8 ms 43136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 13 ms 43136 KB Execution killed with signal 11 (could be triggered by violating memory limits)