oj.uz

Submission #61896

# Submission time Handle Problem Language Result Execution time Memory
61896 2018-07-27T04:41:04 Z 노영훈(#1796) Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 460 ms 38036 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++;
    }

    while(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 372 ms 37556 KB Output is correct
2 Correct 371 ms 37808 KB Output is correct
3 Correct 359 ms 37872 KB Output is correct
4 Correct 460 ms 37872 KB Output is correct
5 Correct 328 ms 37872 KB Output is correct
6 Correct 405 ms 37936 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 37936 KB Output is correct
2 Correct 312 ms 37936 KB Output is correct
3 Correct 389 ms 37936 KB Output is correct
4 Correct 338 ms 37936 KB Output is correct
5 Correct 357 ms 38036 KB Output is correct
6 Correct 344 ms 38036 KB Output is correct
7 Correct 343 ms 38036 KB Output is correct
8 Correct 269 ms 38036 KB Output is correct
9 Correct 358 ms 38036 KB Output is correct
10 Correct 220 ms 38036 KB Output is correct
11 Correct 241 ms 38036 KB Output is correct
12 Correct 197 ms 38036 KB Output is correct
13 Correct 194 ms 38036 KB Output is correct
14 Correct 255 ms 38036 KB Output is correct