Submission #867527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867527	2023-10-28T15:02:35 Z	bibinm	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	167 ms	100280 KB

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.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	92696 KB	Output is correct
2	Correct	155 ms	92616 KB	Output is correct
3	Correct	167 ms	92780 KB	Output is correct
4	Correct	153 ms	92616 KB	Output is correct
5	Correct	159 ms	92696 KB	Output is correct
6	Correct	153 ms	92608 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	92696 KB	Output is correct
2	Correct	161 ms	92832 KB	Output is correct
3	Correct	154 ms	92864 KB	Output is correct
4	Correct	154 ms	92500 KB	Output is correct
5	Correct	154 ms	92724 KB	Output is correct
6	Correct	156 ms	92700 KB	Output is correct
7	Correct	160 ms	92816 KB	Output is correct
8	Correct	156 ms	92616 KB	Output is correct
9	Correct	151 ms	94096 KB	Output is correct
10	Correct	139 ms	97980 KB	Output is correct
11	Correct	146 ms	96432 KB	Output is correct
12	Correct	129 ms	100220 KB	Output is correct
13	Correct	124 ms	100276 KB	Output is correct
14	Correct	126 ms	100280 KB	Output is correct