#include <bits/stdc++.h>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
const int inf = 2e9;
const int N = 1e6 + 15;
int n, k, a[N];
struct node {
node *prev, *next;
int val;
node(int val) : val(val) {
prev = next = NULL;
}
};
typedef node* pnode;
vector <pnode> fr;
pnode root, last;
stack <pair <int, pnode> > st, temp;
void processnext() {
while(last) {
int now = last->val;
while(!st.empty() && st.top().f == now) {
st.pop();
++now;
}
while(k && !st.empty() && st.top().f < now) {
pnode x = new node(st.top().f);
x->prev = st.top().se;
x->next = st.top().se->next;
if(x->next)
x->next->prev = x;
if(x->prev)
x->prev->next = x;
fr.pb(x);
int curval = x->val;
while(!st.empty() && st.top().f == curval)
st.pop(), ++curval;
st.push(mp(curval, x));
--k;
}
while(!st.empty() && st.top().f == now) {
st.pop();
++now;
}
st.push(mp(now, last));
last = last->next;
}
}
void addelse() {
while(!st.empty()) {
int now = st.top().f;
temp.push(st.top());
st.pop();
while(!st.empty() && st.top().f > now + 1) {
int need = st.top().f - 1;
pnode x = new node(need);
x->prev = st.top().se;
x->next = st.top().se->next;
if(x->next)
x->next->prev = x;
if(x->prev)
x->prev->next = x;
fr.pb(x);
st.push(mp(need, x));
--k;
}
}
}
void checkend() {
deque <pair <int, pnode> > s;
while(!temp.empty()) {
st.push(temp.top());
s.push_back(temp.top());
temp.pop();
}
while(!s.empty() && s.front().f != 30) {
if(s.front() < s.back()) {
last = s.front().se;
pnode x = new node(s.front().f);
x->next = last;
int now = x->val;
if(x->next)
x->next->prev = x;
fr.pb(x);
--k;
while(!s.empty() && s.front().f == now) {
s.pop_front();
++now;
}
}
else {
last = s.back().se;
pnode x = new node(s.back().f);
x->prev = last;
int now = x->val;
if(x->prev)
x->prev->next = x;
fr.pb(x);
--k;
while(!s.empty() && s.back().f == now) {
s.pop_back();
++now;
}
}
}
}
void extend_fr() {
while(!fr.empty() && k) {
pnode x = fr.back();
fr.ppb();
if(x->val <= 1)
continue;
pnode a = new node(x->val - 1), b = new node(x->val - 1);
a->prev = x->prev;
a->next = b;
b->prev = a;
b->next = x->next;
if(b->next)
b->next->prev = b;
if(a->prev)
a->prev->next = a;
fr.pb(a);
fr.pb(b);
--k;
}
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
root = new node(a[1]);
last = root;
for(int i = 2; i <= n; ++i) {
pnode x = new node(a[i]);
x->prev = last;
last->next = x;
last = x;
}
last = root;
processnext();
addelse();
checkend();
extend_fr();
last = root;
deque <int> cur;
while(last) {
cur.push_back(last->val);
last = last->next;
}
if(cur.size() != n + k) {
while(root) {
printf("%d ", root->val);
root = root->next;
}
return 0;
}
fr.clear();
cur.clear();
while(!temp.empty())
temp.pop();
while(!st.empty())
st.pop();
root = new node(a[n]);
last = root;
for(int i = n - 1; i; --i) {
pnode x = new node(a[i]);
x->next = last;
last->prev = x;
last = x;
}
last = root;
processnext();
addelse();
checkend();
extend_fr();
while(last) {
cur.push_front(last->val);
last = last->next;
}
for(int i = 0; i < cur.size(); ++i)
printf("%d ", cur[i]);
return 0;
}
Compilation message
zalmoxis.cpp: In function 'void processnext()':
zalmoxis.cpp:52:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(x->prev)
^~
zalmoxis.cpp:54:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
fr.pb(x);
^~
zalmoxis.cpp: In function 'void extend_fr()':
zalmoxis.cpp:143:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(a->prev)
^~
zalmoxis.cpp:145:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
fr.pb(a);
^~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:174:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cur.size() != n + k) {
~~~~~~~~~~~^~~~~~~~
zalmoxis.cpp:204:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cur.size(); ++i)
~~^~~~~~~~~~~~
zalmoxis.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
259 ms |
42284 KB |
Output is correct |
| 2 |
Correct |
260 ms |
42412 KB |
Output is correct |
| 3 |
Correct |
260 ms |
42356 KB |
Output is correct |
| 4 |
Correct |
261 ms |
42360 KB |
Output is correct |
| 5 |
Correct |
260 ms |
42340 KB |
Output is correct |
| 6 |
Correct |
259 ms |
42360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
42320 KB |
Output is correct |
| 2 |
Correct |
259 ms |
42488 KB |
Output is correct |
| 3 |
Correct |
259 ms |
42360 KB |
Output is correct |
| 4 |
Correct |
260 ms |
42560 KB |
Output is correct |
| 5 |
Correct |
260 ms |
42360 KB |
Output is correct |
| 6 |
Correct |
264 ms |
42444 KB |
Output is correct |
| 7 |
Correct |
259 ms |
42488 KB |
Output is correct |
| 8 |
Correct |
260 ms |
42488 KB |
Output is correct |
| 9 |
Correct |
253 ms |
44772 KB |
Output is correct |
| 10 |
Incorrect |
239 ms |
58468 KB |
not a zalsequence |
| 11 |
Correct |
243 ms |
52192 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
2 ms |
376 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
2 ms |
376 KB |
Unexpected end of file - int32 expected |
