oj.uz

Submission #300861

# Submission time Handle Problem Language Result Execution time Memory
300861 2020-09-17T14:32:12 Z kaplanbar Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 757 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();
    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--;
                }
                s.pop();
            }
            else {
                break;
            }
        }
        if(i != n) {
            cout << a[i] << " ";
        }
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 648 ms 18252 KB Unexpected end of file - int32 expected
2 Incorrect 658 ms 18248 KB Unexpected end of file - int32 expected
3 Incorrect 640 ms 18248 KB Unexpected end of file - int32 expected
4 Incorrect 641 ms 18252 KB Unexpected end of file - int32 expected
5 Incorrect 653 ms 18244 KB Unexpected end of file - int32 expected
6 Incorrect 660 ms 18240 KB Unexpected end of file - int32 expected

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 672 ms 34736 KB Execution killed with signal 11
2 Runtime error 673 ms 34376 KB Execution killed with signal 11
3 Runtime error 717 ms 34504 KB Execution killed with signal 11
4 Runtime error 714 ms 34760 KB Execution killed with signal 11
5 Runtime error 757 ms 34636 KB Execution killed with signal 11
6 Incorrect 714 ms 18248 KB Unexpected end of file - int32 expected
7 Runtime error 721 ms 34636 KB Execution killed with signal 11
8 Runtime error 750 ms 34760 KB Execution killed with signal 11
9 Runtime error 610 ms 33864 KB Execution killed with signal 11
10 Runtime error 235 ms 16984 KB Execution killed with signal 11
11 Runtime error 358 ms 24112 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 Incorrect 29 ms 384 KB Unexpected end of file - int32 expected