oj.uz

Submission #442168

# Submission time Handle Problem Language Result Execution time Memory
442168 2021-07-07T08:56:50 Z zxcvbnm Zalmoxis (BOI18_zalmoxis) C++14
5 / 100
 304 ms 48396 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();
    }

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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 44200 KB doesn't contain S as a subsequence
2 Incorrect 268 ms 47792 KB doesn't contain S as a subsequence
3 Incorrect 304 ms 46444 KB doesn't contain S as a subsequence
4 Incorrect 278 ms 46652 KB doesn't contain S as a subsequence
5 Incorrect 266 ms 45028 KB doesn't contain S as a subsequence
6 Incorrect 290 ms 46344 KB doesn't contain S as a subsequence

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 262 ms 44548 KB doesn't contain S as a subsequence
2 Incorrect 256 ms 42876 KB doesn't contain S as a subsequence
3 Incorrect 274 ms 48396 KB doesn't contain S as a subsequence
4 Incorrect 264 ms 44836 KB doesn't contain S as a subsequence
5 Incorrect 268 ms 46876 KB doesn't contain S as a subsequence
6 Incorrect 294 ms 45844 KB doesn't contain S as a subsequence
7 Incorrect 262 ms 45780 KB doesn't contain S as a subsequence
8 Incorrect 273 ms 47860 KB doesn't contain S as a subsequence
9 Incorrect 268 ms 38912 KB doesn't contain S as a subsequence
10 Incorrect 259 ms 23252 KB doesn't contain S as a subsequence
11 Incorrect 241 ms 29192 KB doesn't contain S as a subsequence
12 Incorrect 232 ms 11184 KB doesn't contain S as a subsequence
13 Incorrect 284 ms 11296 KB doesn't contain S as a subsequence
14 Correct 231 ms 11408 KB Output is correct