oj.uz

Submission #442165

# Submission time Handle Problem Language Result Execution time Memory
442165 2021-07-07T08:52:49 Z zxcvbnm Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 263 ms 48420 KB 
#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();
    }
    for(int i : ans) {
        cout << i << " ";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 44344 KB Output is correct
2 Correct 236 ms 47896 KB Output is correct
3 Correct 234 ms 46496 KB Output is correct
4 Correct 229 ms 46696 KB Output is correct
5 Correct 233 ms 45072 KB Output is correct
6 Correct 232 ms 46360 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 44560 KB not a zalsequence
2 Incorrect 231 ms 43024 KB not a zalsequence
3 Incorrect 229 ms 48420 KB not a zalsequence
4 Incorrect 263 ms 44948 KB not a zalsequence
5 Incorrect 235 ms 47036 KB not a zalsequence
6 Incorrect 227 ms 45856 KB not a zalsequence
7 Incorrect 231 ms 45812 KB not a zalsequence
8 Incorrect 263 ms 47892 KB not a zalsequence
9 Incorrect 223 ms 38932 KB not a zalsequence
10 Incorrect 211 ms 23432 KB not a zalsequence
11 Incorrect 218 ms 29304 KB not a zalsequence
12 Incorrect 209 ms 11308 KB not a zalsequence
13 Incorrect 214 ms 11180 KB not a zalsequence
14 Incorrect 210 ms 11300 KB not a zalsequence