oj.uz

Submission #61893

# Submission time Handle Problem Language Result Execution time Memory
61893 2018-07-27T04:36:42 Z 노영훈(#1796) Zalmoxis (BOI18_zalmoxis) C++11
40 / 100
 413 ms 38060 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 379 ms 37608 KB Output is correct
2 Correct 323 ms 37836 KB Output is correct
3 Correct 325 ms 37836 KB Output is correct
4 Correct 413 ms 37836 KB Output is correct
5 Correct 387 ms 37888 KB Output is correct
6 Correct 407 ms 37888 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 37948 KB not a zalsequence
2 Correct 306 ms 37948 KB Output is correct
3 Correct 397 ms 38020 KB Output is correct
4 Incorrect 344 ms 38020 KB not a zalsequence
5 Incorrect 354 ms 38020 KB not a zalsequence
6 Incorrect 286 ms 38020 KB not a zalsequence
7 Incorrect 366 ms 38060 KB not a zalsequence
8 Incorrect 294 ms 38060 KB not a zalsequence
9 Incorrect 361 ms 38060 KB not a zalsequence
10 Incorrect 222 ms 38060 KB not a zalsequence
11 Incorrect 251 ms 38060 KB not a zalsequence
12 Incorrect 4 ms 38060 KB Unexpected end of file - int32 expected
13 Incorrect 3 ms 38060 KB Unexpected end of file - int32 expected
14 Incorrect 3 ms 38060 KB Unexpected end of file - int32 expected