oj.uz

Submission #442155

# Submission time Handle Problem Language Result Execution time Memory
442155 2021-07-07T08:36:46 Z zxcvbnm Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 270 ms 50220 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.rbegin(), a.rend());
    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;
                ans.push_back(i);
                break;
            }
        }
    }

    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 252 ms 48300 KB doesn't contain S as a subsequence
2 Incorrect 246 ms 47928 KB doesn't contain S as a subsequence
3 Incorrect 253 ms 46960 KB doesn't contain S as a subsequence
4 Incorrect 260 ms 47416 KB doesn't contain S as a subsequence
5 Incorrect 249 ms 47340 KB doesn't contain S as a subsequence
6 Incorrect 244 ms 45488 KB doesn't contain S as a subsequence

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 48016 KB doesn't contain S as a subsequence
2 Incorrect 242 ms 47980 KB doesn't contain S as a subsequence
3 Incorrect 244 ms 47920 KB doesn't contain S as a subsequence
4 Incorrect 244 ms 48240 KB doesn't contain S as a subsequence
5 Incorrect 247 ms 47528 KB doesn't contain S as a subsequence
6 Incorrect 270 ms 50220 KB doesn't contain S as a subsequence
7 Incorrect 250 ms 48484 KB doesn't contain S as a subsequence
8 Incorrect 245 ms 48132 KB doesn't contain S as a subsequence
9 Incorrect 240 ms 41056 KB doesn't contain S as a subsequence
10 Incorrect 219 ms 23132 KB doesn't contain S as a subsequence
11 Incorrect 224 ms 30084 KB doesn't contain S as a subsequence
12 Incorrect 221 ms 11180 KB doesn't contain S as a subsequence
13 Incorrect 212 ms 11232 KB doesn't contain S as a subsequence
14 Incorrect 215 ms 11240 KB not a zalsequence