oj.uz

Submission #647402

# Submission time Handle Problem Language Result Execution time Memory
647402 2022-10-02T11:53:59 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 176 ms 31904 KB 
#include <bits/stdc++.h>

using namespace std;

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);

	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->inserted = (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->inserted = false;
		size++;
		stck.pop();
	}

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

	linkedListNode *hd = head->next;

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

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

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

			newNode->inserted = (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 153 ms 31820 KB Output is correct
2 Correct 166 ms 31828 KB Output is correct
3 Correct 168 ms 31876 KB Output is correct
4 Correct 158 ms 31812 KB Output is correct
5 Correct 176 ms 31896 KB Output is correct
6 Correct 165 ms 31880 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 31848 KB Output is correct
2 Correct 173 ms 31844 KB Output is correct
3 Correct 155 ms 31808 KB Output is correct
4 Correct 162 ms 31824 KB Output is correct
5 Correct 162 ms 31904 KB Output is correct
6 Correct 161 ms 31804 KB Output is correct
7 Correct 154 ms 31820 KB Output is correct
8 Correct 159 ms 31780 KB Output is correct
9 Correct 143 ms 30168 KB Output is correct
10 Correct 112 ms 27060 KB Output is correct
11 Correct 126 ms 28052 KB Output is correct
12 Correct 84 ms 25740 KB Output is correct
13 Correct 85 ms 25792 KB Output is correct
14 Correct 93 ms 25708 KB Output is correct