#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;
m-=(ans.size()-n);
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()-1<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()-1);
while(!st.empty()){
ra.pb(st.top());
st.pop();
}
}
if(ra.size()!=n+k)assert(0);
for(auto i:ra)cout<<i<<" ";
}
Compilation message
zalmoxis.cpp: In function 'int32_t main()':
zalmoxis.cpp:63: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]
63 | for(int i=0;i<ans.size();i++){
| ~^~~~~~~~~~~
zalmoxis.cpp:71:39: 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]
71 | while(!st.empty()&&st.size()-1<m){
| ~~~~~~~~~~~^~
zalmoxis.cpp:89: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]
89 | if(ra.size()!=n+k)assert(0);
| ~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
29884 KB |
Output is correct |
| 2 |
Correct |
105 ms |
29632 KB |
Output is correct |
| 3 |
Correct |
116 ms |
28612 KB |
Output is correct |
| 4 |
Correct |
104 ms |
28448 KB |
Output is correct |
| 5 |
Correct |
106 ms |
30008 KB |
Output is correct |
| 6 |
Correct |
116 ms |
28356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
29884 KB |
Output is correct |
| 2 |
Correct |
107 ms |
28488 KB |
Output is correct |
| 3 |
Correct |
110 ms |
29816 KB |
Output is correct |
| 4 |
Correct |
125 ms |
28952 KB |
Output is correct |
| 5 |
Correct |
105 ms |
28616 KB |
Output is correct |
| 6 |
Correct |
117 ms |
28632 KB |
Output is correct |
| 7 |
Correct |
112 ms |
29888 KB |
Output is correct |
| 8 |
Correct |
117 ms |
30656 KB |
Output is correct |
| 9 |
Correct |
116 ms |
27588 KB |
Output is correct |
| 10 |
Correct |
88 ms |
16856 KB |
Output is correct |
| 11 |
Correct |
99 ms |
23276 KB |
Output is correct |
| 12 |
Correct |
80 ms |
10328 KB |
Output is correct |
| 13 |
Correct |
61 ms |
10408 KB |
Output is correct |
| 14 |
Correct |
62 ms |
10416 KB |
Output is correct |
