#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1000007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, k, a[M];
vector <int> pos[M];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
vector < pair <int,int> > v(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
v[i] = {a[i], i};
}
for(int j = 1; j < 30; ++j){
vector < pair <int,int> > nw;
int cur = 0;
for(int i = 0; i < v.size(); ++i){
if(cur){
if(nw.back().F != v[i].F){
int last = nw.back().S;
pos[nw.back().S].pb(j);
nw.pop_back();
nw.pb({j + 1, last});
nw.pb(v[i]);
--k;
}
else{
nw.pop_back();
nw.pb({j + 1, v[i].S});
}
cur = 0;
}
else{
nw.pb(v[i]);
cur += (v[i].F == j);
}
}
if(cur){
--k;
nw.pop_back();
nw.pb({j + 1, v.back().S});
pos[nw.back().S].pb(j);
}
v = nw;
}
int cur = 0;
for(int i = 0; i < n; ++i){
cout << a[i] << " ";
for(auto j : pos[i]){
if(k){
cout << j - 1 << " ";
--k;
int cur = j - 1;
while(k-- && cur > 1) cout << --cur << " ";
cout << cur << " ";
}
else cout << j << " ";
}
}
cout << endl;
return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < v.size(); ++i){
| ~~^~~~~~~~~~
zalmoxis.cpp:70:9: warning: unused variable 'cur' [-Wunused-variable]
70 | int cur = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
82252 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1081 ms |
82632 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1085 ms |
84184 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1092 ms |
84200 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1087 ms |
83388 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1087 ms |
84724 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
83968 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1095 ms |
81908 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1096 ms |
82536 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1095 ms |
82652 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1085 ms |
82316 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1085 ms |
82528 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1092 ms |
83584 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1075 ms |
84560 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1098 ms |
80732 KB |
Time limit exceeded |
| 10 |
Incorrect |
658 ms |
54236 KB |
Expected EOF |
| 11 |
Execution timed out |
1097 ms |
71152 KB |
Time limit exceeded |
| 12 |
Incorrect |
13 ms |
23756 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
12 ms |
23756 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
15 ms |
23780 KB |
Unexpected end of file - int32 expected |
