oj.uz

Submission #442460

# Submission time Handle Problem Language Result Execution time Memory
442460 2021-07-07T18:42:52 Z JovanB Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 265 ms 61212 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using T = pair <int, pair <int, int>>;

const int MAXN = 1000000;

vector <int> dod[MAXN+5];
vector <T> vec;
vector <T> nvec;

int a[MAXN+5];

void pisi(int x, int times){
    if(times == 1){
        cout << x << " ";
        return;
    }
    if((1<<(x-1)) >= times-1){
        pisi(x-1, times-1);
        cout << x-1 << " ";
        return;
    }
    else{
        pisi(x-1, (1<<(x-1)));
        times -= (1<<(x-1));
        pisi(x-1, times);
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        vec.push_back({a[i], {i, i}});
    }
    for(int j=0; j<=29; j++){
        nvec.clear();
        //for(auto c : vec) cout << c.first << " " << c.second.first << " " << c.second.second << endl;
        for(int i=0; i<vec.size(); i++){
            if(vec[i].first == j){
                if(i == vec.size()-1 || vec[i+1].first != j){
                    dod[vec[i].second.second].push_back(j);
                    nvec.push_back({j+1, vec[i].second});
                }
                else{
                    nvec.push_back({j+1, {vec[i].second.first, vec[i+1].second.second}});
                    i++;
                }
            }
            else nvec.push_back(vec[i]);
        }
        //cout << endl;
        vec.clear();
        for(auto c : nvec) vec.push_back(c);
    }
    for(int i=1; i<=n; i++){
        m -= dod[i].size();
    }
    for(int i=1; i<=n; i++){
        cout << a[i] << " ";
        for(auto c : dod[i]){
            if((1<<c)-1 <= m){
                m -= (1<<c)-1;
                pisi(c, (1<<c));
            }
            else{
                pisi(c, m+1);
                m = 0;
            }
        }
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=0; i<vec.size(); i++){
      |                      ~^~~~~~~~~~~
zalmoxis.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 if(i == vec.size()-1 || vec[i+1].first != j){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 59936 KB Output is correct
2 Correct 255 ms 59924 KB Output is correct
3 Correct 259 ms 59924 KB Output is correct
4 Correct 253 ms 59928 KB Output is correct
5 Correct 255 ms 59924 KB Output is correct
6 Correct 251 ms 59920 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 59984 KB Output is correct
2 Correct 249 ms 59924 KB Output is correct
3 Correct 254 ms 59860 KB Output is correct
4 Correct 253 ms 59928 KB Output is correct
5 Correct 257 ms 59924 KB Output is correct
6 Correct 258 ms 59924 KB Output is correct
7 Correct 261 ms 59876 KB Output is correct
8 Correct 260 ms 59924 KB Output is correct
9 Correct 262 ms 61212 KB Output is correct
10 Correct 169 ms 40772 KB Output is correct
11 Correct 202 ms 46236 KB Output is correct
12 Correct 104 ms 25796 KB Output is correct
13 Correct 104 ms 25792 KB Output is correct
14 Correct 108 ms 25820 KB Output is correct