Submission #867494

#	Time	Username	Problem	Language	Result	Execution time	Memory
867494		andrej246	Zalmoxis (BOI18_zalmoxis)	C++14	5 / 100	180 ms	76972 KiB

zalmoxis

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

#define FOR(i,N) for(long long i = 0; (i) < (N); (i)++)
#define FORS(i,v,N) for(long long i = v; (i) < (N); (i)++)
#define FORI(i,v,N,inc) for(long long i = v; (i) < (N); (i)+=(inc))
#define NL '\n'
#define EL cout << NL
#define PRINTV(v) for(auto a:(v)) {cout << a << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}
#define STRP(p) "{" << (p).first << "," << (p).second << "}"
#define PRINTVP(v) for(auto a:(v)) {cout << STRP(a) << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;



vl partsplit(ll num, ll t) {
    vl res;
    vl count(num+1);
    ll amount = 1;
    count[num] = 1;
    while(amount < t) {
        FORS(i,1,num+1) {
            if (count[i] > 0) {
                count[i]--;
                count[i-1]+=2;
                break;
            }
        }
        //PRINTV(count);
        //scout << amount << NL;
        amount++;
    }
    FOR(i,num+1) {
        FOR(_,count[i]) {
            res.push_back(i);
        }
    }
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    ll N,K;
    cin >> N >> K;
    vl s(N);
    FOR(i,N) cin >> s[i];

    vvl changes(N);
    vl index(N);
    vl cur_s = s;
    ll cur_n = N;
    ll new_len = N;

    FOR(i,N) {
        index[i] = i;
    }

    FOR(x,30) {
        bool prev = false;
        vl next_s;
        vl next_index;
        ll next_n = 0;
        ll cur_index = 0;
        FOR(i,cur_n) {
            if (cur_s[i] == x) {
                if (prev == false) prev = true;
                else {
                    prev = false;
                    next_s.push_back(x+1);
                    next_n++;
                    next_index.push_back(cur_index);
                    cur_index++;
                }
            } else {
                if (prev == true) {
                    changes[index[i-1]].push_back(x);
                    new_len++;
                    prev = false;
                    next_s.push_back(x+1);
                    next_n++;
                    next_index.push_back(cur_index);
                    cur_index++;
                }
                next_s.push_back(cur_s[i]);
                next_index.push_back(cur_index);
                cur_index++;
                next_n++;
            }
        }
        if (prev == true) {
            changes[index[cur_n-1]].push_back(x);
            new_len++;
            prev = false;
            next_s.push_back(x+1);
            next_n++;
            next_index.push_back(cur_index);
            cur_index++;
        }
        cur_s = next_s;
        index = next_index;
        cur_n = next_n;
        //PRINTV(cur_s);
        //PRINTV(index);
        //PRINTVP(changes);
    }
    //PRINTVV(changes);
    vl new_s;
    ll target = N + K - new_len;
    assert(target >= 0);

    FOR(i,N) {
        new_s.push_back(s[i]);
        for (auto x:changes[i]) {
            if (target == 0)
                new_s.push_back(x);
            else if (target >= pow(2,x)-1) {
                FOR(_,pow(2,x)) {
                    new_s.push_back(0);
                }
                target -= pow(2,x)-1;
            } else {
                vl part = partsplit(x,target+1);
                for (auto v: part) {
                    new_s.push_back(v);
                }
                target = 0;
            }
        }
    }
    PRINTV(new_s);

    return 0;
}

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