oj.uz

Submission #644533

# Submission time Handle Problem Language Result Execution time Memory
644533 2022-09-24T20:46:24 Z Kripton Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 147 ms 36188 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;
    int rez=0;
    v[0]=-1;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        rez+=(1<<v[i]);
        v1[i]=v[i];
        while(vf&&v[i]>v[steve[vf]])
        {
            addie[steve[vf]].push_back(v[steve[vf]]);
            rez+=(1<<v[steve[vf]]);
            v[steve[vf]]++;
            while(vf&&v[steve[vf]]==v[steve[vf-1]])
            {
                v[steve[vf-1]]++;
                vf--;
            }
        }
        while(v[i]==v[steve[vf]])
        {
            v[i]++;
            vf--;
        }
        steve[++vf]=i;
    }
    while(v[steve[vf]]!=30)
    {
        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[i];
    }
    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 144 ms 33744 KB Output is correct
2 Correct 136 ms 33620 KB Output is correct
3 Correct 145 ms 33736 KB Output is correct
4 Correct 137 ms 33740 KB Output is correct
5 Correct 147 ms 33648 KB Output is correct
6 Correct 136 ms 33608 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 33740 KB Expected EOF
2 Incorrect 136 ms 33696 KB Expected EOF
3 Incorrect 144 ms 33812 KB Expected EOF
4 Incorrect 143 ms 33648 KB Expected EOF
5 Incorrect 142 ms 33768 KB Expected EOF
6 Incorrect 135 ms 33660 KB Expected EOF
7 Incorrect 140 ms 33724 KB Expected EOF
8 Incorrect 137 ms 33696 KB Expected EOF
9 Incorrect 145 ms 36188 KB Expected EOF
10 Incorrect 98 ms 31344 KB Expected EOF
11 Incorrect 114 ms 33944 KB Expected EOF
12 Incorrect 53 ms 25808 KB Expected EOF
13 Incorrect 52 ms 25832 KB Expected EOF
14 Correct 52 ms 25704 KB Output is correct