Submission #90984

#	Time	Username	Problem	Language	Result	Execution time	Memory
90984		choikiwon	Zalmoxis (BOI18_zalmoxis)	C++17	25 / 100	1098 ms	148304 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;
    }
};
set<Seg> st;
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++) {
        st.insert({ i, i, A[i] });
    }
    for(int n = 0; n < 30; n++) {
        vector<Seg> seg;
        for(auto it = st.begin(); it != st.end(); it++) {
            if(it->v == n) {
                seg.push_back(*it);
            }
        }
        for(int i = 0; i < seg.size(); i++) {
            if(i == (int)seg.size() - 1 || seg[i].r + 1 != seg[i + 1].l) {
                st.erase(seg[i]);
                st.insert({ seg[i].l, seg[i].r, seg[i].v + 1 });
                add[ seg[i].r ].push_back(n);
                K--;
            }
            else {
                st.erase(seg[i]);
                st.erase(seg[i + 1]);
                st.insert({ seg[i].l, seg[i + 1].r, seg[i].v + 1 });
                i++;
            }
        }
    }

    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:54:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < seg.size(); i++) {
                        ~~^~~~~~~~~~~~
zalmoxis.cpp:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < add[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~
zalmoxis.cpp:38: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:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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