oj.uz

Submission #722329

# Submission time Handle Problem Language Result Execution time Memory
722329 2023-04-11T18:31:08 Z groshi Zalmoxis (BOI18_zalmoxis) C++17
70 / 100
 652 ms 75036 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 74940 KB Output is correct
2 Correct 591 ms 74936 KB Output is correct
3 Correct 598 ms 74828 KB Output is correct
4 Correct 596 ms 74900 KB Output is correct
5 Correct 589 ms 74848 KB Output is correct
6 Correct 571 ms 74944 KB Output is correct

Subtask #2
40.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 74872 KB Output is correct
2 Correct 591 ms 74860 KB Output is correct
3 Correct 574 ms 74972 KB Output is correct
4 Correct 652 ms 74884 KB Output is correct
5 Correct 599 ms 75036 KB Output is correct
6 Correct 612 ms 74808 KB Output is correct
7 Correct 626 ms 74872 KB Output is correct
8 Correct 611 ms 74920 KB Output is correct
9 Incorrect 542 ms 68900 KB Unexpected end of file - int32 expected
10 Incorrect 276 ms 32500 KB Unexpected end of file - int32 expected
11 Incorrect 404 ms 48560 KB Unexpected end of file - int32 expected
12 Incorrect 88 ms 2240 KB Unexpected end of file - int32 expected
13 Incorrect 80 ms 2216 KB Unexpected end of file - int32 expected
14 Incorrect 88 ms 2252 KB Unexpected end of file - int32 expected