Submission #442460

#	Time	Username	Problem	Language	Result	Execution time	Memory
442460		JovanB	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	265 ms	61212 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70