Submission #130692

#	Time	Username	Problem	Language	Result	Execution time	Memory
130692		Vardanyan	Zalmoxis (BOI18_zalmoxis)	C++14	65 / 100	1081 ms	30488 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
const int N = 1000*1000+5;
int A[N];
int main(){
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
  //  if(k!=1) assert(0);
    vector<pair<int,int> > a;
    for(int i = 1;i<=n;i++){
            cin>>A[i];
            a.push_back({A[i],1});
    }
    int qan = 0;
    while(1){
        stack<pair<int,int> > st;
        for(int i = 0;i<a.size();i++){
            if(!st.size()){
                st.push({a[i].first,i});
                continue;
            }
            st.push({a[i].first,i});
            while(st.size()>=2){
                pair<int,int> x = st.top();
                st.pop();
                pair<int,int> y = st.top();
                st.pop();
                if(x.first != y.first){
                    st.push(y);
                    st.push(x);
                    break;
                }
                st.push({x.first+1,x.second});
            }
        }
        if(st.size() == 1){
            int x = st.top().first;
            if(x == 30) break;
        }
        int mn = 1000*1000*1000+5;
        int id = 0;
        while(st.size()){
            int x = st.top().first;
            int y = st.top().second;
            if(x<mn){
                mn = x;
                id = y;
            }
            st.pop();
        }
     //   cout<<mn<<endl;
        bool f = false;
        vector<pair<int,int> > nw;
        qan++;
        for(int i = 0;i<a.size();i++){
          //  cout<<a[i]<<" ";
            nw.push_back({a[i].first,a[i].second});
            if(i == id){
              //  cout<<mn<<" ";
              //  f = true;
              nw.push_back({mn,-1});
            }
        }
        a = nw;
    }

    int dif = k-qan;
    vector<int> ans;
    for(int i = 0;i<a.size();i++){
         //   cout<<a[i].first<<" ";
        if(a[i].second == 1){
          //  cout<<a[i].first<<" ";
            ans.push_back(a[i].first);
            continue;
        }
        ans.push_back(a[i].first);
        while(dif){
            int qn = log2(dif);
            if(dif == 1) qn++;
            if(ans.back() == 1) break;
            if(ans.back()-qn<=0){
                qn = ans.back()-1;
            }
           // if(qn == 0) break;
            int x = ans.back();
            ans.pop_back();
            for(int j = 0;j<(1<<qn);j++){
            //    cout<<a[i].first-qn<<" ";
                ans.push_back(x-qn);
            }
            dif-=((1<<qn)-1);
            //a[i].first = a[i].first-qn;
        }
    }
    for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";

    cout<<endl;
    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<a.size();i++){
                       ~^~~~~~~~~
zalmoxis.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<a.size();i++){
                       ~^~~~~~~~~
zalmoxis.cpp:53:14: warning: unused variable 'f' [-Wunused-variable]
         bool f = false;
              ^
zalmoxis.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<a.size();i++){
                   ~^~~~~~~~~
zalmoxis.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
                   ~^~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 35 / 70