Submission #442168

#	Time	Username	Problem	Language	Result	Execution time	Memory
442168		zxcvbnm	Zalmoxis (BOI18_zalmoxis)	C++14	5 / 100	304 ms	48396 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
    int l, r, par;
    bool active;
};
vector<Node> tree[31];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Node root;
    root.l = -1, root.r = -1, root.par = -1, root.active = true;
    tree[30].push_back(root);
    stack<int> can_use[31];
    can_use[30].push(0);

    int n, nxt;
    cin >> n >> nxt;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

//    sort(a.begin(), a.end());
    vector<int> ans;
    for(int i : a) {
        for(int j = i; j <= 30; j++) {
            if (!can_use[j].empty()) {
                for(int k = j; k > i; k--) {
                    int v = can_use[k].top();
                    can_use[k].pop();

                    Node c;
                    c.l = -1;
                    c.r = -1;
                    c.par = v;
                    c.active = true;
                    tree[k-1].push_back(c);
                    tree[k-1].push_back(c);
                    int idx1 = (int) tree[k-1].size()-2;
                    int idx2 = (int) tree[k-1].size()-1;
                    can_use[k-1].push(idx1);
                    can_use[k-1].push(idx2);

                    tree[k][v].active = false;
                    tree[k][v].l = idx1;
                    tree[k][v].r = idx2;
                }

                int v = can_use[i].top();
                can_use[i].pop();
                tree[i][v].active = false;
                break;
            }
        }
        ans.push_back(i);
    }

    priority_queue<int> rec;
    for(int i = 30; i >= 1; i--) {
        while(!can_use[i].empty()) {
            can_use[i].pop();
            rec.push(i);
        }
    }

    while((int) rec.size() != nxt) {
        int v = rec.top();
        assert(v != 1);
        rec.pop();
        rec.push(v-1);
        rec.push(v-1);
    }

    while(!rec.empty()) {
        ans.push_back(rec.top());
        rec.pop();
    }

    sort(ans.begin(), ans.end());

    for(int i : ans) {
        cout << i << " ";
    }
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 5 / 70