oj.uz

답안 #867482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867482 2023-10-28T13:16:10 Z andrej246 Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 199 ms 74040 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;
    ll pow = 1;
    ll val = num-1;
    while (t) {
        if (t % 2) {
            FOR(_,pow) {
                res.push_back(val);
            }
        }
        t /= 2;
        pow *= 2;
        val --;
    }
    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);
    }
    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 178 ms 69224 KB not a zalsequence
2 Incorrect 170 ms 69096 KB not a zalsequence
3 Incorrect 155 ms 69296 KB not a zalsequence
4 Incorrect 170 ms 68620 KB not a zalsequence
5 Incorrect 160 ms 69436 KB not a zalsequence
6 Incorrect 162 ms 68924 KB not a zalsequence

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 164 ms 67912 KB not a zalsequence
2 Incorrect 162 ms 74040 KB not a zalsequence
3 Incorrect 169 ms 73996 KB not a zalsequence
4 Incorrect 195 ms 67628 KB not a zalsequence
5 Incorrect 164 ms 67708 KB not a zalsequence
6 Incorrect 169 ms 67644 KB not a zalsequence
7 Incorrect 165 ms 67984 KB not a zalsequence
8 Incorrect 199 ms 68680 KB not a zalsequence
9 Incorrect 181 ms 64744 KB not a zalsequence
10 Incorrect 105 ms 35928 KB not a zalsequence
11 Incorrect 135 ms 43668 KB not a zalsequence
12 Incorrect 64 ms 14896 KB not a zalsequence
13 Incorrect 64 ms 12880 KB not a zalsequence
14 Incorrect 61 ms 12540 KB not a zalsequence