oj.uz

답안 #867519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867519 2023-10-28T14:48:45 Z bibinm Zalmoxis (BOI18_zalmoxis) C++17
15 / 100
 132 ms 100300 KB 
#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(){
    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;
        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 79920 KB Execution killed with signal 11
2 Runtime error 41 ms 79700 KB Execution killed with signal 11
3 Runtime error 37 ms 79904 KB Execution killed with signal 11
4 Runtime error 37 ms 79696 KB Execution killed with signal 11
5 Runtime error 38 ms 79964 KB Execution killed with signal 11
6 Runtime error 38 ms 79860 KB Execution killed with signal 11

Subtask #2
15.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 38 ms 79700 KB Execution killed with signal 11
2 Runtime error 38 ms 79700 KB Execution killed with signal 11
3 Runtime error 40 ms 79568 KB Execution killed with signal 11
4 Runtime error 37 ms 79708 KB Execution killed with signal 11
5 Runtime error 40 ms 79952 KB Execution killed with signal 11
6 Runtime error 37 ms 79956 KB Execution killed with signal 11
7 Runtime error 37 ms 79696 KB Execution killed with signal 11
8 Runtime error 36 ms 79696 KB Execution killed with signal 11
9 Runtime error 30 ms 63828 KB Execution killed with signal 11
10 Runtime error 12 ms 24412 KB Execution killed with signal 11
11 Runtime error 19 ms 40128 KB Execution killed with signal 11
12 Correct 129 ms 100280 KB Output is correct
13 Correct 132 ms 100300 KB Output is correct
14 Correct 129 ms 100280 KB Output is correct