Submission #909800

#	Time	Username	Problem	Language	Result	Execution time	Memory
909800		8pete8	Zalmoxis (BOI18_zalmoxis)	C++17	30 / 100	289 ms	262144 KiB

zalmoxis

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,ll>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
using namespace std;
#define int long long
#define double long double
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
const int mod=1e9+7,mxn=3e5,lg=30,inf=1e18,minf=-1e9,Mxn=100000;
int n,m;
int32_t main(){
    fastio
    cin>>n>>m;
    vector<int>v(n),ans;
    for(int i=0;i<n;i++)cin>>v[i];
    deque<int>dq;
    dq.pb(30);
    for(int i=0;i<n;i++){
        while(!dq.empty()&&dq.front()<v[i]){
            ans.pb(dq.front());
            dq.pop_front();
        }
        int k=dq.front();
        dq.pop_front();
        for(int j=k;j>v[i];j--)dq.push_front(j-1);
        ans.pb(v[i]);
    }
    while(!dq.empty()){
        ans.pb(dq.front());
        dq.pop_front();
    }
    int cur=0,tmp=0,k=m;
    vector<int>ra;
    for(int i=0;i<ans.size();i++){
        if(cur<n&&v[cur]==ans[i]){
            cur++;
            ra.pb(ans[i]);
            continue;
        }
        stack<int>st;
        st.push(ans[i]);
        while(!st.empty()&&st.size()<m){
            while(!st.empty()&&st.top()==0){
                ra.pb(0);
                m--;
                st.pop();
            }
            if(st.empty())break;
            tmp=st.top();
            st.pop();
            st.push(tmp-1);
            st.push(tmp-1);
        }
        m-=st.size();
        while(!st.empty()){
            ra.pb(st.top());
            st.pop();
        }
    }
    if(ra.size()!=n+k)assert(0);
    for(auto i:ra)cout<<i<<" ";
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int32_t main()':
zalmoxis.cpp:62:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~
zalmoxis.cpp:70:37: warning: comparison of integer expressions of different signedness: 'std::stack<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   70 |         while(!st.empty()&&st.size()<m){
      |                            ~~~~~~~~~^~
zalmoxis.cpp:88:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |     if(ra.size()!=n+k)assert(0);
      |        ~~~~~~~~~^~~~~

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