oj.uz

Submission #61890

# Submission time Handle Problem Language Result Execution time Memory
61890 2018-07-27T04:34:50 Z 노영훈(#1796) Zalmoxis (BOI18_zalmoxis) C++11
40 / 100
 414 ms 73368 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, bool> pib;
const int MX=1000010, inf=2e9;

int n, k;
int A[MX];

void comp(vector<int> &V){
    int sz=V.size();
    while(sz>1 && V[sz-2]==V[sz-1]){
        V.pop_back(), V[sz-2]++, sz--;
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>A[i];
    vector<int> V;
    list<pib> B;

    for(int i=1; i<=n; i++) B.push_back({A[i], false});

    for(auto it=B.begin(); it!=B.end();){
        if(V.empty()) { V.push_back(it->first); it++; continue; }
        if(V.back()<it->first) { B.insert(it, {V.back(), true}); it--; continue; }
        V.push_back(it->first);
        comp(V);
        it++;
    }
    if(V.back()!=30) B.push_back({V.back(), true}), V.push_back(V.back());
    comp(V);
    assert(V[0]==30);

    for(auto it=B.begin(); it!=B.end();){
        if((int)B.size()>=n+k) break;
        if(!(it->second) || it->first==0) { it++; continue; }
        it->first--;
        B.insert(it, *it);
        it--;
    }
    assert((int)B.size()==n+k);

    for(pib &p:B) cout<<p.first<<' ';

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 37752 KB Output is correct
2 Correct 414 ms 37752 KB Output is correct
3 Correct 380 ms 37752 KB Output is correct
4 Correct 290 ms 37752 KB Output is correct
5 Correct 338 ms 37824 KB Output is correct
6 Correct 320 ms 37876 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 71256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 298 ms 73368 KB Output is correct
3 Correct 282 ms 73368 KB Output is correct
4 Runtime error 232 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 253 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 283 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 247 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 255 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 269 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 104 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 141 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 9 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 1 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 73368 KB Execution killed with signal 11 (could be triggered by violating memory limits)