oj.uz

Submission #442159

# Submission time Handle Problem Language Result Execution time Memory
442159 2021-07-07T08:40:40 Z zxcvbnm Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 259 ms 45284 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 43740 KB doesn't contain S as a subsequence
2 Incorrect 245 ms 44524 KB doesn't contain S as a subsequence
3 Incorrect 253 ms 44652 KB doesn't contain S as a subsequence
4 Incorrect 242 ms 44632 KB doesn't contain S as a subsequence
5 Incorrect 241 ms 44496 KB doesn't contain S as a subsequence
6 Incorrect 246 ms 44228 KB doesn't contain S as a subsequence

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 45284 KB doesn't contain S as a subsequence
2 Incorrect 246 ms 43200 KB doesn't contain S as a subsequence
3 Incorrect 243 ms 44124 KB doesn't contain S as a subsequence
4 Incorrect 239 ms 44012 KB doesn't contain S as a subsequence
5 Incorrect 259 ms 44312 KB doesn't contain S as a subsequence
6 Incorrect 246 ms 44948 KB doesn't contain S as a subsequence
7 Incorrect 245 ms 44524 KB doesn't contain S as a subsequence
8 Incorrect 244 ms 43936 KB doesn't contain S as a subsequence
9 Incorrect 237 ms 37540 KB doesn't contain S as a subsequence
10 Incorrect 227 ms 22756 KB doesn't contain S as a subsequence
11 Incorrect 217 ms 29320 KB doesn't contain S as a subsequence
12 Incorrect 211 ms 11184 KB doesn't contain S as a subsequence
13 Incorrect 210 ms 11308 KB doesn't contain S as a subsequence
14 Incorrect 213 ms 11180 KB not a zalsequence