oj.uz

Submission #90984

# Submission time Handle Problem Language Result Execution time Memory
90984 2018-12-25T11:49:25 Z choikiwon Zalmoxis (BOI18_zalmoxis) C++17
25 / 100
 1000 ms 148304 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;
    }
};
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

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

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 121488 KB Time limit exceeded
2 Execution timed out 1077 ms 123492 KB Time limit exceeded
3 Execution timed out 1098 ms 125648 KB Time limit exceeded
4 Execution timed out 1093 ms 127544 KB Time limit exceeded
5 Execution timed out 1098 ms 129700 KB Time limit exceeded
6 Execution timed out 1096 ms 132020 KB Time limit exceeded

Subtask #2
25.0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 133964 KB Time limit exceeded
2 Execution timed out 1091 ms 136076 KB Time limit exceeded
3 Execution timed out 1095 ms 137884 KB Time limit exceeded
4 Execution timed out 1092 ms 140068 KB Time limit exceeded
5 Execution timed out 1095 ms 142232 KB Time limit exceeded
6 Execution timed out 1079 ms 144380 KB Time limit exceeded
7 Execution timed out 1097 ms 146220 KB Time limit exceeded
8 Execution timed out 1090 ms 148304 KB Time limit exceeded
9 Execution timed out 1080 ms 148304 KB Time limit exceeded
10 Correct 560 ms 148304 KB Output is correct
11 Correct 965 ms 148304 KB Output is correct
12 Correct 117 ms 148304 KB Output is correct
13 Correct 116 ms 148304 KB Output is correct
14 Correct 118 ms 148304 KB Output is correct