Submission #867487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867487	2023-10-28T13:50:05 Z	bibinm	Zalmoxis (BOI18_zalmoxis)	C++17	15 / 100	85 ms	79872 KB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

struct node{
    int val;
    node* prev = nullptr;
    node* next = nullptr;
    node* left = nullptr;
    node* right = nullptr;
};

vector<int> result;

void dfs(node* v){
    if(v->left == nullptr and v->right == nullptr){
        result.push_back(v->val);
        return;
    }

    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-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;
    }

    dfs(cur);    

    while(count_ins < k){
        int r = result.back();
        result.pop_back();
        result.push_back(r-1);
        result.push_back(r-1);

        count_ins += 1;
    }


    for(int &r: result) cout << r << " ";
    cout << "\n";
}

Subtask #1

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	38 ms	79700 KB	Execution killed with signal 11
2	Runtime error	37 ms	79708 KB	Execution killed with signal 11
3	Runtime error	45 ms	79700 KB	Execution killed with signal 11
4	Runtime error	41 ms	79732 KB	Execution killed with signal 11
5	Runtime error	37 ms	79704 KB	Execution killed with signal 11
6	Runtime error	37 ms	79704 KB	Execution killed with signal 11

Subtask #2

15.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	37 ms	79696 KB	Execution killed with signal 11
2	Runtime error	37 ms	79704 KB	Execution killed with signal 11
3	Runtime error	37 ms	79700 KB	Execution killed with signal 11
4	Runtime error	37 ms	79872 KB	Execution killed with signal 11
5	Runtime error	37 ms	79696 KB	Execution killed with signal 11
6	Runtime error	37 ms	79708 KB	Execution killed with signal 11
7	Runtime error	38 ms	79764 KB	Execution killed with signal 11
8	Runtime error	39 ms	79704 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	40028 KB	Execution killed with signal 11
12	Correct	75 ms	12356 KB	Output is correct
13	Correct	71 ms	12328 KB	Output is correct
14	Correct	85 ms	12292 KB	Output is correct