oj.uz

답안 #74056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
74056 2018-08-29T16:49:21 Z vex Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 261 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<<" ";
                d=0;
            }
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 15200 KB Output is correct
2 Correct 228 ms 15472 KB Output is correct
3 Correct 213 ms 15528 KB Output is correct
4 Correct 199 ms 15528 KB Output is correct
5 Correct 261 ms 15568 KB Output is correct
6 Correct 222 ms 15568 KB Output is correct

Subtask #2
5.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 235 ms 15568 KB Expected EOF
2 Incorrect 237 ms 15828 KB Expected EOF
3 Incorrect 234 ms 15888 KB Expected EOF
4 Incorrect 216 ms 15888 KB Expected EOF
5 Incorrect 233 ms 15888 KB Expected EOF
6 Incorrect 229 ms 15888 KB Expected EOF
7 Incorrect 207 ms 15888 KB Expected EOF
8 Incorrect 210 ms 15888 KB Expected EOF
9 Incorrect 240 ms 16492 KB Expected EOF
10 Incorrect 123 ms 16492 KB not a zalsequence
11 Incorrect 168 ms 16492 KB not a zalsequence
12 Incorrect 68 ms 16492 KB not a zalsequence
13 Incorrect 58 ms 16492 KB not a zalsequence
14 Correct 52 ms 16492 KB Output is correct