oj.uz

Submission #647185

# Submission time Handle Problem Language Result Execution time Memory
647185 2022-10-01T20:51:56 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 104 ms 56092 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;

	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++) {
		while (values[i] > stck.top().value || (stck.top().left && stck.top().right)) {
			btNode &top = stck.top();
			if (!top.right && top.value != 0) {
				tail->next = get_new_lnkd_node();
				tail = tail->next;
				tail->val = top.value - 1;
				if (top.value == 1) tail->inserted = false;
				else tail->inserted = true;
				top.right = true;
			}
			stck.pop();
		}

		tail->next = get_new_lnkd_node();
		tail = tail->next;
		tail->val = values[i];
		tail->inserted = false;

		while (stck.top().value != values[i]) {
			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.size() > 1 && stck.top().left && stck.top().right) {
			btNode &top = stck.top();
			if (!top.right && top.value != 0) {
				tail->next = get_new_lnkd_node();
				tail = tail->next;
				tail->val = top.value - 1;
				if (top.value == 1) tail->inserted = false;
				else tail->inserted = true;
				top.right = true;
			}
			stck.pop();
		}
		// maybe this works idk
	}

	while (!stck.empty()) {
		btNode top = stck.top();
		if (!top.right && top.value != 0) {
			tail->next = get_new_lnkd_node();
			tail = tail->next;
			tail->val = top.value - 1;
			if (top.value == 1) tail->inserted = false;
			else 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 86 ms 56004 KB Execution killed with signal 11
2 Runtime error 89 ms 56012 KB Execution killed with signal 11
3 Runtime error 95 ms 56004 KB Execution killed with signal 11
4 Runtime error 85 ms 56008 KB Execution killed with signal 11
5 Runtime error 98 ms 55988 KB Execution killed with signal 11
6 Runtime error 95 ms 56016 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 55976 KB Execution killed with signal 11
2 Runtime error 93 ms 55996 KB Execution killed with signal 11
3 Runtime error 89 ms 55996 KB Execution killed with signal 11
4 Runtime error 104 ms 55996 KB Execution killed with signal 11
5 Runtime error 89 ms 56016 KB Execution killed with signal 11
6 Runtime error 87 ms 56092 KB Execution killed with signal 11
7 Runtime error 85 ms 56020 KB Execution killed with signal 11
8 Runtime error 91 ms 56012 KB Execution killed with signal 11
9 Runtime error 75 ms 54336 KB Execution killed with signal 11
10 Runtime error 47 ms 50376 KB Execution killed with signal 11
11 Runtime error 58 ms 51968 KB Execution killed with signal 11
12 Runtime error 31 ms 48008 KB Execution killed with signal 11
13 Runtime error 31 ms 47956 KB Execution killed with signal 11
14 Incorrect 11 ms 23764 KB Unexpected end of file - int32 expected