#include <bits/stdc++.h>
using namespace std;
const int N = 1000*1000+5;
int A[N];
int main(){
ios_base::sync_with_stdio(false);
int n,k;
cin>>n>>k;
// if(k!=1) assert(0);
vector<pair<int,int> > a;
for(int i = 1;i<=n;i++){
cin>>A[i];
a.push_back({A[i],1});
}
int qan = 0;
while(1){
stack<pair<int,int> > st;
for(int i = 0;i<a.size();i++){
if(!st.size()){
st.push({a[i].first,i});
continue;
}
st.push({a[i].first,i});
while(st.size()>=2){
pair<int,int> x = st.top();
st.pop();
pair<int,int> y = st.top();
st.pop();
if(x.first != y.first){
st.push(y);
st.push(x);
break;
}
st.push({x.first+1,x.second});
}
}
if(st.size() == 1){
int x = st.top().first;
if(x == 30) break;
}
int mn = 1000*1000*1000+5;
int id = 0;
while(st.size()){
int x = st.top().first;
int y = st.top().second;
if(x<mn){
mn = x;
id = y;
}
st.pop();
}
// cout<<mn<<endl;
bool f = false;
vector<pair<int,int> > nw;
qan++;
for(int i = 0;i<a.size();i++){
// cout<<a[i]<<" ";
nw.push_back({a[i].first,a[i].second});
if(i == id){
// cout<<mn<<" ";
// f = true;
nw.push_back({mn,-1});
}
}
a = nw;
}
int dif = k-qan;
vector<int> ans;
for(int i = 0;i<a.size();i++){
// cout<<a[i].first<<" ";
if(a[i].second == 1){
// cout<<a[i].first<<" ";
ans.push_back(a[i].first);
continue;
}
ans.push_back(a[i].first);
while(dif){
int qn = log2(dif);
if(dif == 1) qn++;
if(ans.back() == 1) break;
if(ans.back()-qn<=0){
qn = ans.back()-1;
}
// if(qn == 0) break;
int x = ans.back();
ans.pop_back();
for(int j = 0;j<(1<<qn);j++){
// cout<<a[i].first-qn<<" ";
ans.push_back(x-qn);
}
dif-=((1<<qn)-1);
//a[i].first = a[i].first-qn;
}
}
for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<a.size();i++){
~^~~~~~~~~
zalmoxis.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<a.size();i++){
~^~~~~~~~~
zalmoxis.cpp:53:14: warning: unused variable 'f' [-Wunused-variable]
bool f = false;
^
zalmoxis.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<a.size();i++){
~^~~~~~~~~
zalmoxis.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
24404 KB |
Output is correct |
| 2 |
Correct |
277 ms |
24408 KB |
Output is correct |
| 3 |
Correct |
279 ms |
24404 KB |
Output is correct |
| 4 |
Correct |
272 ms |
24428 KB |
Output is correct |
| 5 |
Correct |
274 ms |
24408 KB |
Output is correct |
| 6 |
Correct |
272 ms |
24552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
698 ms |
30272 KB |
Output is correct |
| 2 |
Execution timed out |
1080 ms |
30344 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1075 ms |
30488 KB |
Time limit exceeded |
| 4 |
Correct |
829 ms |
30348 KB |
Output is correct |
| 5 |
Correct |
586 ms |
30352 KB |
Output is correct |
| 6 |
Correct |
463 ms |
30212 KB |
Output is correct |
| 7 |
Correct |
461 ms |
30416 KB |
Output is correct |
| 8 |
Correct |
706 ms |
30356 KB |
Output is correct |
| 9 |
Execution timed out |
1081 ms |
27036 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1076 ms |
11724 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1077 ms |
16388 KB |
Time limit exceeded |
| 12 |
Incorrect |
83 ms |
6368 KB |
doesn't contain S as a subsequence |
| 13 |
Runtime error |
5 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Correct |
80 ms |
6368 KB |
Output is correct |
