oj.uz

Submission #300826

# Submission time Handle Problem Language Result Execution time Memory
300826 2020-09-17T14:06:42 Z kaplanbar Zalmoxis (BOI18_zalmoxis) C++14
40 / 100
 783 ms 34760 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();
    int total = 0;
    for(int i = 0; i <= n; i++) {
        while(s.size()) {
            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 << " ";
                total++;
                s.pop();
            }
            else {
                break;
            }
        }
        if(i != n) {
            cout << a[i] << " ";
            total++;
        }
    }
    assert(total == n + k);
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 18248 KB Output is correct
2 Correct 677 ms 18248 KB Output is correct
3 Correct 649 ms 18320 KB Output is correct
4 Correct 666 ms 18376 KB Output is correct
5 Correct 671 ms 18376 KB Output is correct
6 Correct 660 ms 18376 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 695 ms 34648 KB Execution killed with signal 11
2 Runtime error 661 ms 34632 KB Execution killed with signal 11
3 Runtime error 664 ms 34504 KB Execution killed with signal 11
4 Runtime error 684 ms 34628 KB Execution killed with signal 11
5 Runtime error 692 ms 34748 KB Execution killed with signal 11
6 Correct 664 ms 18248 KB Output is correct
7 Runtime error 674 ms 34636 KB Execution killed with signal 11
8 Runtime error 783 ms 34760 KB Execution killed with signal 11
9 Runtime error 582 ms 34084 KB Execution killed with signal 11
10 Runtime error 218 ms 16984 KB Execution killed with signal 11
11 Runtime error 384 ms 24280 KB Execution killed with signal 11
12 Runtime error 2 ms 512 KB Execution killed with signal 11
13 Runtime error 1 ms 512 KB Execution killed with signal 11
14 Correct 114 ms 2296 KB Output is correct