Submission #867507

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867507	2023-10-28T14:22:26 Z	bibinm	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	153 ms	100276 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;

int to_add;

void dfs(node* v){
    //cout << v->val << " " << to_add << "\n";
    if(v->left == nullptr and v->right == nullptr){
        if(to_add == 0 || 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-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	79704 KB	Execution killed with signal 11
2	Runtime error	43 ms	79792 KB	Execution killed with signal 11
3	Runtime error	45 ms	79696 KB	Execution killed with signal 11
4	Runtime error	42 ms	79744 KB	Execution killed with signal 11
5	Runtime error	38 ms	79772 KB	Execution killed with signal 11
6	Runtime error	38 ms	79748 KB	Execution killed with signal 11

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	37 ms	79812 KB	Execution killed with signal 11
2	Runtime error	40 ms	79568 KB	Execution killed with signal 11
3	Runtime error	37 ms	79696 KB	Execution killed with signal 11
4	Runtime error	37 ms	79772 KB	Execution killed with signal 11
5	Runtime error	40 ms	79704 KB	Execution killed with signal 11
6	Runtime error	38 ms	79704 KB	Execution killed with signal 11
7	Runtime error	37 ms	79696 KB	Execution killed with signal 11
8	Runtime error	48 ms	79828 KB	Execution killed with signal 11
9	Runtime error	30 ms	63832 KB	Execution killed with signal 11
10	Runtime error	12 ms	24156 KB	Execution killed with signal 11
11	Runtime error	19 ms	40216 KB	Execution killed with signal 11
12	Incorrect	153 ms	100132 KB	doesn't contain S as a subsequence
13	Incorrect	137 ms	100276 KB	doesn't contain S as a subsequence
14	Incorrect	145 ms	100236 KB	doesn't contain S as a subsequence