oj.uz

Submission #578609

# Submission time Handle Problem Language Result Execution time Memory
578609 2022-06-17T11:17:24 Z FatihSolak Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 189 ms 18304 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> create(int a,int b){
    if(b == 1){
        return {a};
    }
    auto l = create(a-1,b/2);
    auto r = create(a-1,b-b/2);
    for(auto u:r){
        l.push_back(u);
    }
    return l;
}
void solve(){
    int n,k;
    cin >> n >> k;
    vector<pair<int,int>> v;
    vector<int> now = {30};
    for(int i = 1;i<=n;i++){
        int x;
        cin >> x;
        while(now.back() < x){
            v.push_back({now.back(),1});
            now.pop_back();
        }
        while(now.back() > x){
            int tmp = now.back()-1;
            now.pop_back();
            now.push_back(tmp);
            now.push_back(tmp);
        }
        v.push_back({now.back(),0});
        now.pop_back();
    }
    while(now.size()){
        v.push_back({now.back(),1});
        now.pop_back();
    }
    vector<int> ans;
    int needed = n + k -  v.size();
    for(auto u:v){
        auto tmp = create(u.first,(u.second?min(1<<u.first,needed+1):1));
        for(auto c:tmp){
            ans.push_back(c);
        }
        needed -= tmp.size() - 1;
    }
    assert(ans.size() == n + k);
    for(auto u:ans){
        cout << u << " ";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from zalmoxis.cpp:1:
zalmoxis.cpp: In function 'void solve()':
zalmoxis.cpp:49:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     assert(ans.size() == n + k);
      |            ~~~~~~~~~~~^~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 18280 KB Output is correct
2 Correct 168 ms 18240 KB Output is correct
3 Correct 169 ms 18192 KB Output is correct
4 Correct 160 ms 18208 KB Output is correct
5 Correct 163 ms 18224 KB Output is correct
6 Correct 189 ms 18240 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 18204 KB Output is correct
2 Correct 177 ms 18204 KB Output is correct
3 Correct 153 ms 18208 KB Output is correct
4 Correct 175 ms 18304 KB Output is correct
5 Correct 156 ms 18252 KB Output is correct
6 Correct 173 ms 18200 KB Output is correct
7 Correct 166 ms 18160 KB Output is correct
8 Correct 180 ms 18168 KB Output is correct
9 Correct 172 ms 17836 KB Output is correct
10 Correct 137 ms 10516 KB Output is correct
11 Correct 156 ms 16188 KB Output is correct
12 Correct 134 ms 7996 KB Output is correct
13 Correct 141 ms 8004 KB Output is correct
14 Correct 129 ms 7976 KB Output is correct