oj.uz

Submission #644525

# Submission time Handle Problem Language Result Execution time Memory
644525 2022-09-24T20:11:15 Z Kripton Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 1000 ms 48084 KB 
#include <bits/stdc++.h>
using namespace std;
int steve[1000001],vf;
int steve1[1000001],vf1;
int v[1000001],v1[1000001];
vector <int> addie[1000001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k,i,j;
    cin>>n>>k;
    v[0]=-1;
    int rez=0;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        rez+=(1<<v[i]);
        v1[i]=v[i];
        while(v[i]==v[steve[vf]])
        {
            v[i]++;
            vf--;
        }
        steve[++vf]=i;
    }
    for(j=1;v[steve[vf]]!=30;j++)
    {
        int min1=40;
        for(i=1;i<=vf;i++)
            min1=min(min1,v[steve[i]]);
        vf1=0;
        for(i=1;i<=vf;i++)
        {
            if(v[steve[i]]==min1)
            {
                k--;
                v[steve[i]]++;
                addie[steve[i]].push_back(min1);
                rez+=(1<<min1);
            }
            while(v[steve[i]]==v[steve1[vf1]])
            {
                v[steve[i]]++;
                vf1--;
            }
            steve1[++vf1]=steve[i];
        }
        vf=vf1;
        for(i=1;i<=vf;i++)
            steve[i]=steve1[vf1];
    }
    assert(rez==(1<<30));
    for(i=1;i<=n;i++)
    {
        cout<<v1[i]<<" ";
        rez+=(1<<v1[i]);
        for(auto it:addie[i])
        {
            if(k>=((1<<it)-1))
            {
                k-=((1<<it)-1);
                for(j=1;j<=(1<<it);j++)
                    cout<<"0 ";
                rez+=(1<<it);
                continue;
            }
            else if(k)
            {
                int a=(int)log2(k)+1;
                int newit=it-a;
                //daca fac (1<<a) newit-uri, k-=((1<<a)-1)
                k=((1<<a)-1)-k;
                for(j=1;j<=(1<<a)-2*k;j++)
                    cout<<newit<<" ";
                rez+=(1<<newit)*((1<<a)-2*k);
                for(j=1;j<=k;j++)
                    cout<<newit+1<<" ";
                rez+=(1<<(newit+1))*k;
                k=0;
            }
            else
            {
                cout<<it<<" ";
                rez+=(1<<it);
            }
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 33660 KB Output is correct
2 Correct 130 ms 33720 KB Output is correct
3 Correct 131 ms 33660 KB Output is correct
4 Correct 134 ms 33724 KB Output is correct
5 Correct 131 ms 33744 KB Output is correct
6 Correct 140 ms 33632 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 31572 KB Time limit exceeded
2 Execution timed out 1094 ms 31628 KB Time limit exceeded
3 Execution timed out 1094 ms 31692 KB Time limit exceeded
4 Execution timed out 1093 ms 31604 KB Time limit exceeded
5 Execution timed out 1097 ms 31564 KB Time limit exceeded
6 Execution timed out 1095 ms 31560 KB Time limit exceeded
7 Execution timed out 1095 ms 31568 KB Time limit exceeded
8 Execution timed out 1093 ms 31552 KB Time limit exceeded
9 Execution timed out 1089 ms 32844 KB Time limit exceeded
10 Execution timed out 1096 ms 27980 KB Time limit exceeded
11 Execution timed out 1048 ms 30284 KB Time limit exceeded
12 Runtime error 30 ms 48076 KB Execution killed with signal 6
13 Runtime error 30 ms 48084 KB Execution killed with signal 6
14 Correct 55 ms 25944 KB Output is correct