Submission #867508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867508	2023-10-28T14:22:27 Z	andrej246	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	196 ms	73656 KB

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;
        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(index[i]);
                }
            } 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(index[i-1]);
                }
                next_s.push_back(cur_s[i]);
                next_index.push_back(index[i]);
                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(index[cur_n-1]);
        }
        cur_s = next_s;
        index = next_index;
        cur_n = next_n;
        //sPRINTV(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

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	68040 KB	Output is correct
2	Correct	173 ms	69192 KB	Output is correct
3	Correct	172 ms	68980 KB	Output is correct
4	Correct	171 ms	68244 KB	Output is correct
5	Correct	192 ms	67668 KB	Output is correct
6	Correct	176 ms	69232 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	69216 KB	Output is correct
2	Correct	163 ms	73656 KB	Output is correct
3	Correct	169 ms	72136 KB	Output is correct
4	Correct	177 ms	69228 KB	Output is correct
5	Correct	163 ms	67944 KB	Output is correct
6	Correct	196 ms	68776 KB	Output is correct
7	Correct	171 ms	68600 KB	Output is correct
8	Correct	175 ms	67660 KB	Output is correct
9	Correct	177 ms	64892 KB	Output is correct
10	Correct	112 ms	35384 KB	Output is correct
11	Correct	136 ms	45560 KB	Output is correct
12	Correct	75 ms	13648 KB	Output is correct
13	Correct	65 ms	13908 KB	Output is correct
14	Correct	63 ms	13396 KB	Output is correct