답안 #867515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867515	2023-10-28T14:43:50 Z	bibinm	Zalmoxis (BOI18_zalmoxis)	C++17	15 / 100	138 ms	100488 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;

    //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

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	37 ms	79708 KB	Execution killed with signal 11
2	Runtime error	40 ms	79700 KB	Execution killed with signal 11
3	Runtime error	38 ms	79696 KB	Execution killed with signal 11
4	Runtime error	41 ms	79716 KB	Execution killed with signal 11
5	Runtime error	37 ms	79700 KB	Execution killed with signal 11
6	Runtime error	38 ms	79952 KB	Execution killed with signal 11

Subtask #2

15.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	36 ms	79696 KB	Execution killed with signal 11
2	Runtime error	37 ms	79692 KB	Execution killed with signal 11
3	Runtime error	36 ms	79696 KB	Execution killed with signal 11
4	Runtime error	43 ms	79664 KB	Execution killed with signal 11
5	Runtime error	37 ms	79708 KB	Execution killed with signal 11
6	Runtime error	38 ms	79708 KB	Execution killed with signal 11
7	Runtime error	36 ms	79768 KB	Execution killed with signal 11
8	Runtime error	39 ms	79812 KB	Execution killed with signal 11
9	Runtime error	30 ms	63824 KB	Execution killed with signal 11
10	Runtime error	12 ms	24156 KB	Execution killed with signal 11
11	Runtime error	19 ms	40132 KB	Execution killed with signal 11
12	Correct	138 ms	100172 KB	Output is correct
13	Correct	137 ms	100280 KB	Output is correct
14	Correct	138 ms	100488 KB	Output is correct