Submission #647695

#	Time	Username	Problem	Language	Result	Execution time	Memory
647695		borgar02	Zalmoxis (BOI18_zalmoxis)	C++17	50 / 100	579 ms	73092 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;
struct node {
    node *ch[2];
    bool marked, vis;
    int h;
    node(int h) : ch({NULL, NULL}), marked(false), vis(false), h(h) {}
    node *go_to(int s) { if(ch[s] == NULL) { ch[!s] = new node(h - 1); return ch[s] = new node(h - 1); } return ch[s]; }
    bool cansplit() { return !ch[0] && !ch[1] && h; }
};
node *root = new node(30);
bool add(int x, int curr = 30, node *t = root)
{
//    cout << curr << "\n";
    if(t -> vis) return false;
    if(curr == x && !(t -> ch[0])) { return t -> vis = t -> marked = true;}
    else if(curr == x) return false;
//    cout << "Going left\n";
    bool ok;
    if(!(ok = add(x, curr - 1, t -> go_to(0)))) {
//        cout << "Going right\n";
        ok = add(x, curr - 1, t -> go_to(1));
    }
    if(!ok) t -> vis = true;
    return ok;
}
const int N = 1e6 + 5;
int a[N];
int k;
int cnt;
void count_leaves(node *t = root)
{
    if(t -> ch[0]) {
        count_leaves(t -> ch[0]);
        count_leaves(t -> ch[1]);
    } else if(!t -> marked) cnt++;
}
void dfs(node *t = root)
{
    if(!t -> ch[0] && !t -> marked && k && t -> cansplit()) {
        k--;
        t -> go_to(0);
    }
    if(t -> ch[0]) {
        dfs(t -> ch[0]);
        dfs(t -> ch[1]);
    }
}
vector <int> res;
void dfs2(node *t = root)
{
    if(t -> ch[0]) {
        dfs2(t -> ch[0]);
        dfs2(t -> ch[1]);
    } else res.push_back(t -> h);
}

int main()
{
    root -> go_to(0);
    int n;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        assert(add(a[i]));
    }
    count_leaves();
    int ck = k;
    k -= cnt;
    dfs();
    dfs2();
    assert(res.size() == n + ck);
    for(int x : res)
        cout << x << " ";
    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In constructor 'node::node(int)':
zalmoxis.cpp:8:67: warning: list-initializer for non-class type must not be parenthesized
    8 |     node(int h) : ch({NULL, NULL}), marked(false), vis(false), h(h) {}
      |                                                                   ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from zalmoxis.cpp:1:
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:73:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     assert(res.size() == n + ck);
      |            ~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 70