Submission #647182

#TimeUsernameProblemLanguageResultExecution timeMemory
647182AlenygamZalmoxis (BOI18_zalmoxis)C++14
0 / 100
116 ms262144 KiB
#include <bits/stdc++.h> using namespace std; struct btNode { int8_t value; btNode *left = nullptr; btNode *right = nullptr; }; btNode preallocBt[40000001]; int lastNodeBt = 0; inline btNode* get_new_btNode() { return &preallocBt[lastNodeBt++]; } struct linkedListNode { int8_t val; linkedListNode *next = nullptr; bool inserted = false; }; linkedListNode preallocLinked[2000001]; 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; btNode root = btNode{30, 0, 0}; linkedListNode *head = get_new_lnkd_node(); linkedListNode *tail = head; stack<btNode*> stck; stck.push(&root); for (int i = 0; i < N; i++) { while (values[i] > stck.top()->value || (stck.top()->left != nullptr && stck.top()->right != nullptr)) { btNode *top = stck.top(); if (top->right == nullptr && 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(); } 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 != nullptr) { // I have to go right (left completely explored) top->right = get_new_btNode(); top->right->value = top->value - 1; stck.push(top->right); } else { // I can go left top->left = get_new_btNode(); top->left->value = top->value - 1; stck.push(top->left); } } stck.pop(); // node is == values[i], algorithm would never run next while loop while (stck.size() > 1 && stck.top()->left != nullptr && stck.top()->right != nullptr) { btNode *top = stck.top(); if (top->right == nullptr && 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(); } // maybe this works idk } while (!stck.empty()) { btNode *top = stck.top(); if (top->right == nullptr && 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...