oj.uz

Submission #502692

# Submission time Handle Problem Language Result Execution time Memory
502692 2022-01-06T12:56:31 Z Urvuk3 Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 180 ms 13268 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=1e6,MAXA=5e6+5,INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

ll n,m,k,q,x,y,z,res=0,l,r;
ifstream input;
ofstream output;

#ifdef ONLINE_JUDGE
    #define input cin
    #define output cout
#endif

vector<int> s;
vector<pii> ans;

void Rastavi(int x){
    s.clear();
    s.pb(x);
    while(k && !s.empty()){
        int top=s.back(); s.ppb();
        if(top==1){
            cout<<1<<" ";
        }
        else{
            s.pb(top-1); s.pb(top-1);
            k--;
        }
    }
    while(!s.empty()){
        cout<<s.back()<<" ";
        s.ppb();
    }
}

void Insert(int x){
    while(!s.empty() && x==s.back()){
        s.ppb();
        x++;
    }
    s.pb(x);
}

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n+1;i++){
        if(i<=n) cin>>x;
        else x=30;
        while(!s.empty() && x>s.back()){
            ans.pb({s.back(),1});
            Insert(s.back());
            k--;
        }
        Insert(x);
        if(i<=n) ans.pb({x,0});
    }
    for(auto h:ans){
        if(h.se==0) cout<<h.fi<<" ";
        else Rastavi(h.fi);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        input.open("D:\\UROS\\Programiranje\\input.in",ios::in);
	output.open("D:\\UROS\\Programiranje\\output.out",ios::out|ios::trunc);
    #endif
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 12316 KB Output is correct
2 Correct 140 ms 12380 KB Output is correct
3 Correct 137 ms 12324 KB Output is correct
4 Correct 180 ms 12324 KB Output is correct
5 Correct 157 ms 12572 KB Output is correct
6 Correct 138 ms 12324 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 12324 KB Output is correct
2 Correct 146 ms 12328 KB Output is correct
3 Correct 142 ms 12388 KB Output is correct
4 Correct 142 ms 12412 KB Output is correct
5 Correct 135 ms 12452 KB Output is correct
6 Correct 138 ms 12328 KB Output is correct
7 Correct 165 ms 12428 KB Output is correct
8 Correct 146 ms 12428 KB Output is correct
9 Correct 135 ms 11556 KB Output is correct
10 Correct 120 ms 13268 KB Output is correct
11 Correct 118 ms 9800 KB Output is correct
12 Correct 80 ms 12204 KB Output is correct
13 Correct 112 ms 12196 KB Output is correct
14 Correct 76 ms 2252 KB Output is correct