oj.uz

Submission #300863

# Submission time Handle Problem Language Result Execution time Memory
300863 2020-09-17T14:32:56 Z kaplanbar Zalmoxis (BOI18_zalmoxis) C++14
40 / 100
 680 ms 34796 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 2e6 + 5;
struct Element {
    int x, l, r;
    bool operator<(Element other) const {
        if(x == other.x) {
            return l > other.l;
        }
        return x > other.x;
    }
};
int n, k, a[N];
priority_queue<Element> q;
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        q.push((Element){a[i], i, i});
    }
    vector<pair<int,int>> Ans;
    while(1) {
        if(q.top().x == 30) break;
        int mn = q.top().x;
        pair<int,int> le = make_pair(q.top().l, q.top().r);
        q.pop();
        if(mn == q.top().x && le.second == q.top().l - 1) {
            auto val = (Element){mn + 1, le.first, q.top().r};
            q.pop();
            q.push(val);
        }
        else {
            Ans.push_back(make_pair(mn, le.second + 1));
            q.push((Element){mn + 1, le.first, le.second});
        }
    }
    stack<pair<int,int>> s;
    int len = (int)Ans.size();
    for(int i = len -  1; i >= 0; i--) {
        s.push(Ans[i]);
    }
    int need = k - (int)s.size();
    for(int i = 0; i <= n; i++) {
        while(s.size()) {
            assert(s.top().second >= i);
            if(s.top().second == i) {
                while(need && s.top().first > 0) {
                    int x = s.top().first;
                    s.pop();
                    s.push(make_pair(x - 1, i));
                    s.push(make_pair(x - 1, i));
                    need--;
                }
                cout << s.top().first << " ";
                s.pop();
            }
            else {
                break;
            }
        }
        if(i != n) {
            cout << a[i] << " ";
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 18252 KB Output is correct
2 Correct 649 ms 18368 KB Output is correct
3 Correct 643 ms 18248 KB Output is correct
4 Correct 638 ms 18416 KB Output is correct
5 Correct 666 ms 18340 KB Output is correct
6 Correct 636 ms 18376 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 665 ms 34672 KB Execution killed with signal 11
2 Runtime error 657 ms 34376 KB Execution killed with signal 11
3 Runtime error 666 ms 34632 KB Execution killed with signal 11
4 Runtime error 665 ms 34632 KB Execution killed with signal 11
5 Runtime error 658 ms 34620 KB Execution killed with signal 11
6 Correct 645 ms 18200 KB Output is correct
7 Runtime error 662 ms 34796 KB Execution killed with signal 11
8 Runtime error 680 ms 34632 KB Execution killed with signal 11
9 Runtime error 561 ms 33864 KB Execution killed with signal 11
10 Runtime error 207 ms 16984 KB Execution killed with signal 11
11 Runtime error 354 ms 24152 KB Execution killed with signal 11
12 Runtime error 1 ms 512 KB Execution killed with signal 11
13 Runtime error 2 ms 512 KB Execution killed with signal 11
14 Correct 114 ms 2496 KB Output is correct