oj.uz

답안 #867494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867494 2023-10-28T14:01:02 Z andrej246 Zalmoxis (BOI18_zalmoxis) C++14
5 / 100
 180 ms 76972 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;
        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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 67904 KB not a zalsequence
2 Incorrect 165 ms 69212 KB not a zalsequence
3 Incorrect 169 ms 68728 KB not a zalsequence
4 Incorrect 163 ms 68104 KB not a zalsequence
5 Incorrect 173 ms 68800 KB not a zalsequence
6 Incorrect 159 ms 68396 KB not a zalsequence

Subtask #2
5.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 172 ms 68880 KB not a zalsequence
2 Incorrect 158 ms 76972 KB not a zalsequence
3 Incorrect 180 ms 72136 KB not a zalsequence
4 Incorrect 164 ms 68904 KB not a zalsequence
5 Incorrect 164 ms 68284 KB not a zalsequence
6 Incorrect 160 ms 67500 KB not a zalsequence
7 Incorrect 167 ms 69292 KB not a zalsequence
8 Incorrect 165 ms 68680 KB not a zalsequence
9 Incorrect 165 ms 66032 KB not a zalsequence
10 Incorrect 104 ms 37368 KB not a zalsequence
11 Incorrect 141 ms 44404 KB not a zalsequence
12 Incorrect 63 ms 14672 KB not a zalsequence
13 Incorrect 71 ms 13460 KB not a zalsequence
14 Correct 63 ms 13396 KB Output is correct