oj.uz

Submission #722339

# Submission time Handle Problem Language Result Execution time Memory
722339 2023-04-11T18:45:02 Z groshi Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 512 ms 73212 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N=2*1e6;
int t[2000000];
set<pair<int,int> > secik;
vector<pair<int,int> > stos;
queue<pair<int,int> > moge;
int potega[40];
void pusty(int i,int co)
{
    stos.push_back({i*N,co});
    secik.insert({i*N,co});
}
void powtorzenia()
{
    while(stos.size()>=2 && stos.back().second==stos[stos.size()-2].second)
    {
        int pozycja=max(stos.back().first,stos[stos.size()-2].first);
        int co=stos.back().second;
        stos.pop_back();
        stos.pop_back();
        stos.push_back({pozycja+1,co+1});
    }
}
void rozbij(int co,int ile)
{
    if(co==1 || ile==1)
    {
        cout<<co<<" ";
        return;
    }
    if(ile<=potega[co-2])
    {
        rozbij(co-1,ile-1);
        cout<<co-1<<" ";
    }
    else{
        rozbij(co-1,potega[co-2]);
        ile-=potega[co-2];
        rozbij(co-1,ile);
    }
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>t[i];
    potega[0]=1;
    for(int i=1;i<=30;i++)
        potega[i]=potega[i-1]*2;
    for(int i=1;i<=n;i++)
    {
        if(stos.size()==0)
            pusty(i,t[i]);
        else{
            while(stos.size() && t[i]>stos.back().second)
            {
                k--;
                secik.insert({stos.back().first+1,-stos.back().second});
                int gdzie=stos.back().first;
                int co=stos.back().second;
                stos.pop_back();
                stos.push_back({gdzie+1,co+1});
                powtorzenia();
            }
            if(stos.size()==0)
                pusty(i,t[i]);
            else{
                if(t[i]==stos.back().second)
                {
                    pusty(i,t[i]);
                    powtorzenia();
                }
                else pusty(i,t[i]);
            }
        }
    }
    while(stos.size()>0 && stos.back().second<30)
    {
        k--;
        secik.insert({stos.back().first+1,-stos.back().second});
        int gdzie=stos.back().first;
        int co=stos.back().second;
        stos.pop_back();
        stos.push_back({gdzie+1,co+1});
        powtorzenia();
    }
    for(auto it=secik.begin();it!=secik.end();it++)
    {
        if((*it).second>=0)
            cout<<(*it).second<<" ";
        else{
            rozbij(-(*it).second,k+1);
            k=max(0LL,k+1-potega[-(*it).second-1]);
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 72920 KB Output is correct
2 Correct 512 ms 73196 KB Output is correct
3 Correct 507 ms 73140 KB Output is correct
4 Correct 512 ms 73168 KB Output is correct
5 Correct 476 ms 73072 KB Output is correct
6 Correct 490 ms 73096 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 73156 KB Output is correct
2 Correct 481 ms 73076 KB Output is correct
3 Correct 472 ms 73004 KB Output is correct
4 Correct 466 ms 73212 KB Output is correct
5 Correct 497 ms 73072 KB Output is correct
6 Correct 486 ms 73080 KB Output is correct
7 Correct 471 ms 73036 KB Output is correct
8 Correct 499 ms 73116 KB Output is correct
9 Correct 483 ms 67340 KB Output is correct
10 Correct 235 ms 31788 KB Output is correct
11 Correct 333 ms 47680 KB Output is correct
12 Correct 72 ms 2252 KB Output is correct
13 Correct 78 ms 2228 KB Output is correct
14 Correct 80 ms 2252 KB Output is correct