oj.uz

답안 #867508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867508 2023-10-28T14:22:27 Z andrej246 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 196 ms 73656 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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