Submission #867527

#	Time	Username	Problem	Language	Result	Execution time	Memory
867527		bibinm	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	167 ms	100280 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

struct node{
    bool original = false;
    int val;
    node* prev = nullptr;
    node* next = nullptr;
    node* left = nullptr;
    node* right = nullptr;
};

vector<int> result;

int to_add;

void dfs(node* v){
    //cout << v->val << " " << to_add << endl;
    if(v->left == nullptr and v->right == nullptr){
        if(v->original or to_add <= 0 or v->val <= 0){
            result.push_back(v->val);
            return;
        }

        node* copy_left = new node();
        copy_left->val = v->val - 1;


        node* copy_right = new node();
        copy_right->val = v->val - 1;

        v->left = copy_left;
        v->right = copy_right;

        to_add -= 1;
    }

    if(v->left != nullptr) dfs(v->left);
    if(v->right != nullptr) dfs(v->right);
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, k; cin >> n >> k;
    vector<node> seq(n);
    for(int i = 0; i < n; i++){
        cin >> seq[i].val;
        seq[i].original = true;
        if(i > 0){
            seq[i-1].next = &seq[i];
            seq[i].prev = &seq[i-1];
        }
    }

    node* sentinel_begin = new node();
    sentinel_begin->val = 100;
    sentinel_begin->next = &seq[0];
    seq[0].prev = sentinel_begin;

    node* sentinel_end = new node();
    sentinel_end->val = 101;
    sentinel_end->prev = &seq.back();
    seq.back().next = sentinel_end;

    //cout << "Z" << endl;

    int count_ins = 0;
    node* cur = &seq[0];
    while(cur->val < 30){
        while(cur->next != sentinel_end or cur->prev != sentinel_begin){
            //cout << endl << cur->prev->val << " " << cur->val << " " << cur->next->val << " | ";

            if(cur->prev->val <= cur->val){
                //cout << ".:\n";
                cur = cur->prev;
                continue;
            }

            // :. is guaranteed

            if(cur->val > cur->next->val){
                //cout << ":.\n";
                cur = cur->next;
                continue;
            }


            // need a new node
            node* mid = new node();
            mid->val = cur->val + 1;

            // :.:
            if(cur->prev->val > cur->val and cur->val < cur->next->val){
                // insert operation

                //cout << ":.:\n";
                count_ins += 1;
                node* copy_cur = new node();
                copy_cur->val = cur->val;

                mid->left = cur;
                mid->right = copy_cur;


                mid->prev = cur->prev;
                mid->prev->next = mid;
                mid->next = cur->next;
                mid->next->prev = mid;
            }


            // :..
            if(cur->prev->val > cur->val and cur->val == cur->next->val){

                //cout << ":..\n";
                mid->left = cur;
                mid->right = cur->next;


                mid->prev = cur->prev;
                mid->prev->next = mid;
                mid->next = cur->next->next;
                mid->next->prev = mid;
            }

            cur = mid;
            continue;


            // ..: (cannot happen)
        }

        //cout << "E: " << cur->val << endl;

        if(cur->val == 30) break;

        node* copy_node = new node();
        copy_node->val = cur->val;

        copy_node->next = cur->next;
        copy_node->next->prev = copy_node;
        copy_node->prev = cur;
        copy_node->prev->next = copy_node;
        count_ins += 1;
    }

    //cout << "A" << endl;

    to_add = k - count_ins;
    dfs(cur);    

    //cout << "B" << endl;

    for(int &r: result) cout << r << " ";
    cout << "\n";
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70