oj.uz

Submission #90986

# Submission time Handle Problem Language Result Execution time Memory
90986 2018-12-25T11:55:36 Z choikiwon Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 248 ms 69292 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 68856 KB Output is correct
2 Correct 233 ms 69008 KB Output is correct
3 Correct 239 ms 69164 KB Output is correct
4 Correct 233 ms 69164 KB Output is correct
5 Correct 239 ms 69268 KB Output is correct
6 Correct 229 ms 69268 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 69268 KB Output is correct
2 Correct 221 ms 69268 KB Output is correct
3 Correct 223 ms 69268 KB Output is correct
4 Correct 225 ms 69268 KB Output is correct
5 Correct 222 ms 69276 KB Output is correct
6 Correct 235 ms 69276 KB Output is correct
7 Correct 248 ms 69276 KB Output is correct
8 Correct 232 ms 69292 KB Output is correct
9 Correct 231 ms 69292 KB Output is correct
10 Correct 172 ms 69292 KB Output is correct
11 Correct 221 ms 69292 KB Output is correct
12 Correct 115 ms 69292 KB Output is correct
13 Correct 109 ms 69292 KB Output is correct
14 Correct 116 ms 69292 KB Output is correct