#include <bits/stdc++.h>
using namespace std;
struct btNode {
int value;
bool left;
bool right;
};
struct linkedListNode {
int8_t val;
linkedListNode *next = nullptr;
bool inserted = false;
};
linkedListNode preallocLinked[1000001];
int lastNodeLnkd = 0;
static linkedListNode* get_new_lnkd_node() {
return &preallocLinked[lastNodeLnkd++];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int> values(N);
for (auto &i: values) cin >> i;
values.push_back(30);
linkedListNode *head = get_new_lnkd_node();
linkedListNode *tail = head;
stack<btNode> stck;
stck.push(btNode{30, 0, 0});
for (int i = 0; i < N; i++) {
tail->next = get_new_lnkd_node();
tail = tail->next;
tail->val = values[i];
tail->inserted = false;
while (values[i] < stck.top().value) {
btNode &top = stck.top();
if (top.left) {
// I have to go right (left completely explored)
btNode right;
right.value = top.value - 1;
top.right = true;
stck.push(right);
} else {
// I can go left
btNode left;
left.value = top.value - 1;
top.left = true;
stck.push(left);
}
}
stck.pop(); // node is == values[i], algorithm would never run next while loop
if (i != N - 1) {
while (stck.size() > 1 && (values[i + 1] >= stck.top().value || (stck.top().right && stck.top().left))) {
btNode &top = stck.top();
if (!top.right) {
tail->next = get_new_lnkd_node();
tail = tail->next;
tail->val = top.value - 1;
tail->inserted = true;
}
stck.pop();
}
} else {
while (!stck.empty() && (values[i + 1] >= stck.top().value || (stck.top().right && stck.top().left))) {
btNode &top = stck.top();
if (!top.right) {
tail->next = get_new_lnkd_node();
tail = tail->next;
tail->val = top.value - 1;
tail->inserted = true;
}
stck.pop();
}
}
}
head = head->next;
while (head != nullptr) {
cout << (int)head->val << ' ';
head = head->next;
}
cout << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
448 ms |
31556 KB |
Unexpected end of file - int32 expected |
2 |
Incorrect |
433 ms |
31520 KB |
Unexpected end of file - int32 expected |
3 |
Incorrect |
448 ms |
31548 KB |
Unexpected end of file - int32 expected |
4 |
Incorrect |
447 ms |
31552 KB |
Unexpected end of file - int32 expected |
5 |
Incorrect |
453 ms |
31568 KB |
Unexpected end of file - int32 expected |
6 |
Incorrect |
444 ms |
31552 KB |
Unexpected end of file - int32 expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
470 ms |
31556 KB |
Unexpected end of file - int32 expected |
2 |
Incorrect |
460 ms |
31552 KB |
Unexpected end of file - int32 expected |
3 |
Incorrect |
433 ms |
31560 KB |
Unexpected end of file - int32 expected |
4 |
Incorrect |
447 ms |
31560 KB |
Unexpected end of file - int32 expected |
5 |
Incorrect |
435 ms |
31556 KB |
Unexpected end of file - int32 expected |
6 |
Incorrect |
474 ms |
31552 KB |
Unexpected end of file - int32 expected |
7 |
Incorrect |
452 ms |
31552 KB |
Unexpected end of file - int32 expected |
8 |
Incorrect |
448 ms |
31568 KB |
Unexpected end of file - int32 expected |
9 |
Incorrect |
396 ms |
30008 KB |
Unexpected end of file - int32 expected |
10 |
Incorrect |
146 ms |
26128 KB |
Unexpected end of file - int32 expected |
11 |
Incorrect |
234 ms |
27684 KB |
Unexpected end of file - int32 expected |
12 |
Incorrect |
10 ms |
23772 KB |
Unexpected end of file - int32 expected |
13 |
Incorrect |
15 ms |
23708 KB |
Unexpected end of file - int32 expected |
14 |
Incorrect |
13 ms |
23752 KB |
Unexpected end of file - int32 expected |