Submission #867510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867510	2023-10-28T14:27:50 Z	bibinm	Zalmoxis (BOI18_zalmoxis)	C++17	15 / 100	135 ms	100276 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 << "\n";
    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(){
    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;
        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;

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

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	37 ms	79708 KB	Execution killed with signal 11
2	Runtime error	36 ms	79740 KB	Execution killed with signal 11
3	Runtime error	37 ms	79696 KB	Execution killed with signal 11
4	Runtime error	36 ms	79700 KB	Execution killed with signal 11
5	Runtime error	37 ms	79708 KB	Execution killed with signal 11
6	Runtime error	37 ms	79864 KB	Execution killed with signal 11

Subtask #2

15.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	37 ms	79700 KB	Execution killed with signal 11
2	Runtime error	40 ms	79708 KB	Execution killed with signal 11
3	Runtime error	36 ms	79536 KB	Execution killed with signal 11
4	Runtime error	37 ms	79696 KB	Execution killed with signal 11
5	Runtime error	37 ms	79696 KB	Execution killed with signal 11
6	Runtime error	37 ms	79852 KB	Execution killed with signal 11
7	Runtime error	38 ms	79696 KB	Execution killed with signal 11
8	Runtime error	36 ms	79704 KB	Execution killed with signal 11
9	Runtime error	28 ms	63824 KB	Execution killed with signal 11
10	Runtime error	11 ms	24156 KB	Execution killed with signal 11
11	Runtime error	18 ms	40028 KB	Execution killed with signal 11
12	Correct	135 ms	100212 KB	Output is correct
13	Correct	135 ms	100096 KB	Output is correct
14	Correct	135 ms	100276 KB	Output is correct