| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 127733 | 2019-07-10T04:20:26 Z | abacaba | Zalmoxis (BOI18_zalmoxis) | C++14 | 1000 ms | 262148 KB |
#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;
map <int, vector <pnode> > is;
vector <pnode> fr;
pnode root = NULL, last;
stack <pair <int, pnode> > st;
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
root = new node(a[1]);
is[a[1]].pb(root);
last = root;
for(int i = 2; i <= n; ++i) {
pnode x = new node(a[i]);
x->prev = last;
last->next = x;
last = x;
is[a[i]].pb(x);
}
last = root;
while(last && k) {
int now = last->val;
while(!st.empty() && st.top().f == now) {
st.pop();
++now;
}
while(!st.empty() && st.top().f < now) {
pnode x = new node(st.top().f);
x->next = last;
x->prev = last->prev;
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));
if(!last->next)
break;
last = last->next;
}
stack <pair <int, pnode> > temp;
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 = temp.top().se;
if(x->next)
x->next->prev = x;
if(x->prev)
x->prev->next = x;
fr.pb(x);
st.push(mp(need, x));
--k;
}
}
while(last && k) {
int now = last->val;
while(!st.empty() && st.top().f == now) {
st.pop();
++now;
}
while(!st.empty() && st.top().f < now) {
pnode x = new node(st.top().f);
x->next = last;
x->prev = last->prev;
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));
if(!last->prev)
break;
last = last->prev;
}
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 = temp.top().se;
if(x->next)
x->next->prev = x;
if(x->prev)
x->prev->next = x;
fr.pb(x);
st.push(mp(need, x));
--k;
}
}
st = temp;
if(!st.empty() && st.top().f != 30) {
last = st.top().se;
pnode x = new node(st.top().f);
x->prev = last;
if(x->prev)
x->prev->next = x;
fr.pb(x);
--k;
}
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;
}
while(root) {
printf("%d ", root->val);
root = root->next;
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 592 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Incorrect | 348 ms | 72480 KB | Expected EOF |
| 3 | Incorrect | 316 ms | 56104 KB | Expected EOF |
| 4 | Incorrect | 289 ms | 48232 KB | Expected EOF |
| 5 | Runtime error | 586 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 | Incorrect | 407 ms | 83680 KB | Expected EOF |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 599 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Runtime error | 623 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 | Correct | 305 ms | 45672 KB | Output is correct |
| 4 | Runtime error | 597 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 | Runtime error | 593 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 | Runtime error | 592 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 | Runtime error | 595 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 | Incorrect | 351 ms | 67848 KB | Expected EOF |
| 9 | Execution timed out | 1084 ms | 74380 KB | Time limit exceeded |
| 10 | Execution timed out | 1075 ms | 86840 KB | Time limit exceeded |
| 11 | Execution timed out | 1079 ms | 81092 KB | Time limit exceeded |
| 12 | Incorrect | 2 ms | 376 KB | Unexpected end of file - int32 expected |
| 13 | Execution timed out | 1084 ms | 28408 KB | Time limit exceeded |
| 14 | Incorrect | 2 ms | 256 KB | Unexpected end of file - int32 expected |