Submission #1229911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229911		Ghulam_Junaid	Zalmoxis (BOI18_zalmoxis)	C++20	25 / 100	889 ms	308672 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10, LG = 31;
int n, k, rep[N], sz;
vector<int> S[N];

int root(int v){
    return (rep[v] ? rep[v] = root(rep[v]) : v);
}

void merge(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return ;
    rep[u] = v;
    for (int x : S[u])
        S[v].push_back(x);
    S[u].clear();
}

struct node{
    int val, mn_ind, par, lc, rc;
    node(){
        val = mn_ind = par = lc = rc = -1;
    }
} a[N];

void work(int x){
    if (k == 0 or a[x].val == 0) return ;
    k++;
    
    a[sz].val = a[x].val - 1;
    a[sz].par = x;
    sz++;
    a[sz].val = a[x].val - 1;
    a[sz].par = x;
    sz++;

    a[x].lc = sz - 2, a[x].rc = sz - 1;
    k -= 2;

    work(a[x].lc);
    work(a[x].rc);
}

vector<int> path;
void dfs(int v){
    if (a[v].lc == -1){
        path.push_back(a[v].val);
        return ;
    }

    dfs(a[v].lc);
    dfs(a[v].rc);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i ++){
        cin >> a[i].val;
        a[i].mn_ind = i;
        S[i] = {i};
    }
    sz = n + 1;
    for (int cur = 0; cur < 30; cur ++){
        // cout << ":: " << cur << endl;
        for (int i = 2; i <= n; i ++)
            if (a[i].val <= cur and a[i - 1].val <= cur)
                merge(i, i - 1);

        // cout << cur << " :: " << sz << endl;
        int last = -1;
        for (int i = 1; i <= n; i ++){
            int r = root(i);
            if (r == last) continue;
            last = r;

            vector<pair<int, int>> vec;
            for (int x : S[r]){
                // cout << r << " contains " << x << " which is " << a[x].val << endl;
                if (a[x].val == cur)
                    vec.push_back({a[x].mn_ind, x});
            }
            sort(vec.begin(), vec.end());

            if (vec.size() % 2){
                // cout << "HERE" << endl;
                vec.push_back({sz, sz});
                a[sz].val = cur, a[sz].mn_ind = sz;
                S[sz] = {sz};
                merge(sz, r);
                sz++;
                k--;
            }
            for (int j = 0; j < vec.size(); j += 2){
                int x = vec[j].second, y = vec[j + 1].second;
                // cout << cur << " : " << x << " " << y << endl;
                a[sz].val = cur + 1;
                a[sz].lc = x, a[sz].rc = y;
                a[sz].mn_ind = min(a[x].mn_ind, a[y].mn_ind);
                a[x].par = sz, a[y].par = sz;
                S[sz] = {sz};
                merge(sz, r);
                sz++;
            }
        }

        // cout << cur << " :: " << sz << endl;
    }

    // cout << "Done" << endl;
    // cout << k << endl;
    assert(k >= 0);
    for (int i = n + 1; i < sz; i ++){
        if (a[i].lc != -1) continue;
        work(i);
    }

    // cout << "work done" << endl;

    int r;
    for (int i = 1; i < sz; i ++)
        if (a[i].val == 30)
            r = i;

    // cout << "Root = " << r << endl;

    dfs(r);
    for (int x : path)
        cout << x << " ";
    cout << endl;
}

• Subtask 1: 0 / 30
• Subtask 2: 25 / 70