제출 #722329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722329		groshi	Zalmoxis (BOI18_zalmoxis)	C++17	70 / 100	652 ms	75036 KiB

zalmoxis

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N=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-potega[-(*it).second-1]);
        }
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 40 / 70