Submission #90986

#	Time	Username	Problem	Language	Result	Execution time	Memory
90986		choikiwon	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	248 ms	69292 KiB

zalmoxis

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

const int MN = 2000010;

int N, K;
int A[MN];

struct Seg {
    int l, r, v;
    bool operator <(const Seg &i) const {
        if(l != i.l) return l < i.l;
        if(r != i.r) return r < i.r;
        if(v != i.v) return v < i.v;
        return false;
    }
};
Seg arr[MN];
int nxt[MN];
vector<int> add[MN];

void solve(int v, int c) {
    if(c == 0) return;
    if(c == 1) {
        printf("%d ", v);
        return;
    }
    if(v == 0) {
        printf("%d ", v);
        return;
    }
    int t = min(c - 1, (1 << (v - 1)));
    c -= t;
    solve(v - 1, t);
    solve(v - 1, c);
}

int main() {
    scanf("%d %d", &N, &K);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    for(int i = 0; i < N; i++) {
        arr[i] = { i, i, A[i] };
        nxt[i] = i + 1;
    }
    for(int n = 0; n < 30; n++) {
        int cur = 0;
        while(cur < N) {
            int suc = nxt[cur];
            if(arr[cur].v != n) {
                cur = suc;
                continue;
            }

            if(suc == N || arr[suc].v != n) {
                arr[cur].v++;
                add[ arr[cur].r ].push_back(n);
                K--;
            }
            else {
                arr[cur].r = arr[suc].r;
                arr[cur].v++;
                nxt[cur] = nxt[suc];
            }
            cur = nxt[cur];
        }
    }
    for(int i = 0; i < N; i++) {
        printf("%d ", A[i]);

        for(int j = 0; j < add[i].size(); j++) {
            int t = min(K, (1 << add[i][j]) - 1);
            K -= t;
            solve(add[i][j], t + 1);
        }
    }
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:74:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < add[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~
zalmoxis.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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