oj.uz

Submission #647409

# Submission time Handle Problem Language Result Execution time Memory
647409 2022-10-02T12:23:54 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 154 ms 31568 KB 
#include <bits/stdc++.h>

using namespace std;

struct linkedListNode {
	int8_t val;
	linkedListNode *next = nullptr;
	bool splittable = false;
};

linkedListNode preallocLinked[1000001];
int lastNodeLnkd = 0;
inline 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);

	int size = 0;
	linkedListNode *head = get_new_lnkd_node();
	linkedListNode *tail = head;

	stack<int8_t> stck;
	stck.push(30);

	for (int i = 0; i < N; i++) {
		while (stck.top() < values[i]) {
			tail->next = get_new_lnkd_node();
			tail = tail->next;
			tail->val = stck.top();
			tail->splittable = (stck.top() != 0);
			size++;

			stck.pop();
		}

		while (stck.top() > values[i]) {
			int tmp = stck.top()-1;
			stck.pop();
			stck.push(tmp);
			stck.push(tmp);
		}

		tail->next = get_new_lnkd_node();
		tail = tail->next;
		tail->val = values[i];
		tail->splittable = false;
		size++;
		stck.pop();
	}

	while (stck.size()) {
		tail->next = get_new_lnkd_node();
		tail = tail->next;
		tail->val = stck.top();
		tail->splittable = true;
		size++;
		stck.pop();
	}

	linkedListNode *hd = head->next;

	head = head->next;
	while (head != nullptr) {
		while (size < (N + K) && head->splittable) {
			linkedListNode *newNode = get_new_lnkd_node();
			head->val = head->val - 1;

			head->splittable = (head->val != 0);

			newNode->val = head->val;
			newNode->next = head->next;

			newNode->splittable = (newNode->val != 0);
			head->next = newNode;
			size++;
		}
		head = head->next;
	}

	while (hd != nullptr) {
		cout << (int)hd->val << ' ';
		hd = hd->next;
	}

	cout << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 31568 KB Output is correct
2 Correct 145 ms 31564 KB Output is correct
3 Correct 146 ms 31556 KB Output is correct
4 Correct 143 ms 31556 KB Output is correct
5 Correct 151 ms 31560 KB Output is correct
6 Correct 148 ms 31564 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 31560 KB Output is correct
2 Correct 153 ms 31560 KB Output is correct
3 Correct 148 ms 31560 KB Output is correct
4 Correct 154 ms 31552 KB Output is correct
5 Correct 146 ms 31568 KB Output is correct
6 Correct 143 ms 31560 KB Output is correct
7 Correct 153 ms 31556 KB Output is correct
8 Correct 149 ms 31568 KB Output is correct
9 Correct 140 ms 30028 KB Output is correct
10 Correct 102 ms 26936 KB Output is correct
11 Correct 117 ms 27772 KB Output is correct
12 Correct 80 ms 25680 KB Output is correct
13 Correct 75 ms 25912 KB Output is correct
14 Correct 76 ms 25804 KB Output is correct