oj.uz

Submission #61895

# Submission time Handle Problem Language Result Execution time Memory
61895 2018-07-27T04:38:12 Z 노영훈(#1796) Zalmoxis (BOI18_zalmoxis) C++11
40 / 100
 407 ms 73224 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--;
    }
}
vector<int> V;
list<pib> B;

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

    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 392 ms 37588 KB Output is correct
2 Correct 371 ms 37604 KB Output is correct
3 Correct 406 ms 37640 KB Output is correct
4 Correct 339 ms 37792 KB Output is correct
5 Correct 327 ms 37852 KB Output is correct
6 Correct 370 ms 37852 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 241 ms 71180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 356 ms 73224 KB Output is correct
3 Correct 407 ms 73224 KB Output is correct
4 Runtime error 280 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 248 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 251 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 245 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 214 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 283 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 110 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 141 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 10 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 73224 KB Execution killed with signal 11 (could be triggered by violating memory limits)