oj.uz

Submission #647186

# Submission time Handle Problem Language Result Execution time Memory
647186 2022-10-01T20:56:30 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 84 ms 56020 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 (stck.size() > 1 && 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;
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:39:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   39 |   while (stck.size() > 1 && values[i] > stck.top().value || (stck.top().left && stck.top().right)) {
      |          ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 56008 KB Execution killed with signal 11
2 Runtime error 77 ms 56000 KB Execution killed with signal 11
3 Runtime error 77 ms 55996 KB Execution killed with signal 11
4 Runtime error 84 ms 56016 KB Execution killed with signal 11
5 Runtime error 82 ms 55960 KB Execution killed with signal 11
6 Runtime error 80 ms 55956 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 56016 KB Execution killed with signal 11
2 Runtime error 80 ms 56000 KB Execution killed with signal 11
3 Runtime error 79 ms 55996 KB Execution killed with signal 11
4 Runtime error 77 ms 55976 KB Execution killed with signal 11
5 Runtime error 77 ms 56020 KB Execution killed with signal 11
6 Runtime error 77 ms 56004 KB Execution killed with signal 11
7 Runtime error 78 ms 56004 KB Execution killed with signal 11
8 Runtime error 77 ms 55992 KB Execution killed with signal 11
9 Runtime error 68 ms 54344 KB Execution killed with signal 11
10 Runtime error 44 ms 50364 KB Execution killed with signal 11
11 Runtime error 54 ms 52012 KB Execution killed with signal 11
12 Runtime error 30 ms 47948 KB Execution killed with signal 11
13 Runtime error 29 ms 47956 KB Execution killed with signal 11
14 Incorrect 10 ms 23764 KB Unexpected end of file - int32 expected