oj.uz

Submission #300811

# Submission time Handle Problem Language Result Execution time Memory
300811 2020-09-17T13:57:02 Z kaplanbar Zalmoxis (BOI18_zalmoxis) C++14
40 / 100
 693 ms 34764 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e6 + 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;
    for(int i = (int)Ans.size() -  1; i >= 0; i--) {
        s.push(Ans[i]);
    }
    int ptr = 0;
    int need = k - (int)s.size();
    for(int i = 0; i < n + k; i++) {
        while(s.size()) {
            if(s.top().second == i) {
                if(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--;
                }
                else {
                    cout << s.top().first << " ";
                    s.pop();
                }
            }
            else {
                break;
            }
        }
        if(i < n) cout << a[i] << " ";
    }
    assert(s.empty());
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:43:9: warning: unused variable 'ptr' [-Wunused-variable]
   43 |     int ptr = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 18252 KB Output is correct
2 Correct 649 ms 18224 KB Output is correct
3 Correct 649 ms 18248 KB Output is correct
4 Correct 673 ms 18228 KB Output is correct
5 Correct 657 ms 18248 KB Output is correct
6 Correct 654 ms 18248 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 671 ms 34744 KB Execution killed with signal 11
2 Runtime error 664 ms 34504 KB Execution killed with signal 11
3 Runtime error 682 ms 34624 KB Execution killed with signal 11
4 Runtime error 693 ms 34764 KB Execution killed with signal 11
5 Runtime error 688 ms 34632 KB Execution killed with signal 11
6 Correct 650 ms 18248 KB Output is correct
7 Runtime error 674 ms 34760 KB Execution killed with signal 11
8 Runtime error 685 ms 34760 KB Execution killed with signal 11
9 Runtime error 593 ms 34080 KB Execution killed with signal 11
10 Runtime error 210 ms 16984 KB Execution killed with signal 11
11 Runtime error 352 ms 24408 KB Execution killed with signal 11
12 Runtime error 4 ms 512 KB Execution killed with signal 11
13 Runtime error 6 ms 512 KB Execution killed with signal 11
14 Correct 116 ms 2424 KB Output is correct