oj.uz

답안 #74048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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