oj.uz

답안 #867514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867514 2023-10-28T14:42:45 Z bibinm Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 145 ms 100292 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(){
    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 43 ms 79696 KB Execution killed with signal 11
2 Runtime error 37 ms 79704 KB Execution killed with signal 11
3 Runtime error 38 ms 79700 KB Execution killed with signal 11
4 Runtime error 40 ms 79696 KB Execution killed with signal 11
5 Runtime error 39 ms 79700 KB Execution killed with signal 11
6 Runtime error 43 ms 79704 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 79860 KB Execution killed with signal 11
2 Runtime error 37 ms 79696 KB Execution killed with signal 11
3 Runtime error 37 ms 79508 KB Execution killed with signal 11
4 Runtime error 37 ms 79680 KB Execution killed with signal 11
5 Runtime error 36 ms 79784 KB Execution killed with signal 11
6 Runtime error 37 ms 79700 KB Execution killed with signal 11
7 Runtime error 37 ms 79664 KB Execution killed with signal 11
8 Runtime error 36 ms 79852 KB Execution killed with signal 11
9 Runtime error 30 ms 63832 KB Execution killed with signal 11
10 Runtime error 14 ms 24156 KB Execution killed with signal 11
11 Runtime error 22 ms 40028 KB Execution killed with signal 11
12 Incorrect 142 ms 100100 KB Expected integer, but "|" found
13 Incorrect 142 ms 100292 KB Expected integer, but "|" found
14 Incorrect 145 ms 100156 KB Expected integer, but "|" found