oj.uz

Submission #647392

# Submission time Handle Problem Language Result Execution time Memory
647392 2022-10-02T11:21:08 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 119 ms 56384 KB 
#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
		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;
	}
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 56320 KB Execution killed with signal 11
2 Runtime error 82 ms 56316 KB Execution killed with signal 11
3 Runtime error 89 ms 56284 KB Execution killed with signal 11
4 Runtime error 94 ms 56376 KB Execution killed with signal 11
5 Runtime error 88 ms 56360 KB Execution killed with signal 11
6 Runtime error 94 ms 56328 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 56364 KB Execution killed with signal 11
2 Runtime error 86 ms 56324 KB Execution killed with signal 11
3 Runtime error 85 ms 56384 KB Execution killed with signal 11
4 Runtime error 100 ms 56268 KB Execution killed with signal 11
5 Runtime error 119 ms 56368 KB Execution killed with signal 11
6 Runtime error 88 ms 56340 KB Execution killed with signal 11
7 Runtime error 84 ms 56304 KB Execution killed with signal 11
8 Runtime error 94 ms 56340 KB Execution killed with signal 11
9 Runtime error 82 ms 54520 KB Execution killed with signal 11
10 Runtime error 65 ms 50508 KB Execution killed with signal 11
11 Runtime error 63 ms 52140 KB Execution killed with signal 11
12 Runtime error 30 ms 47988 KB Execution killed with signal 11
13 Runtime error 32 ms 48000 KB Execution killed with signal 11
14 Incorrect 11 ms 23744 KB Unexpected end of file - int32 expected