Submission #837890

#	Time	Username	Problem	Language	Result	Execution time	Memory
837890		teo_thrash	Zalmoxis (BOI18_zalmoxis)	C++14	10 / 100	273 ms	20528 KiB

zalmoxis

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn=1e6+3;
const int mod=1e9+7;

int n, k;
int a[maxn];

vector<pii> ans;
stack<int> s;
vector<pii> added; ///.first - number, .second - position to add after

bool cmp(const pii& left, const pii& right){
    if(left.second==right.second){
        return left.first<right.first;
    }
    return left.second<right.second;
}

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>k;

for(int i=0; i<n; i++){
    cin>>a[i];
}

s.push(a[0]);

int curr;

for(int i=1; i<n; i++){
    curr=a[i];

    if(curr==s.top()){
        while(!s.empty() and curr==s.top() ){
            //cerr<<"unishtojavam "<<curr<<" s predhodnoto"<<endl;
            s.pop();
            curr++;
        }
       s.push(curr);
       //cerr<<"slagam "<<curr<<endl<<endl;
       continue;
    }

    if(a[i]>s.top()){

        int to_add=s.top();

        while(s.top()<a[i]){
            added.pb({to_add, i-1});
            //cerr<<"poneje nai-gorniq e "<<s.top()<<" a trqbva da slagam "<<curr<<" dobavqm "<<to_add<<endl;

            curr=to_add;

            while(!s.empty() and curr==s.top() ){
                s.pop();
                curr++;
            }
            s.push(curr);
            to_add=curr;

            //cerr<<"sled butaniq nai-otgore e "<<curr<<endl<<endl;;
        }

        curr=a[i];
        //s.pop();
        while(!s.empty() and curr==s.top() ){
            s.pop();
            curr++;
        }
        s.push(curr);

        continue;
    }
    s.push(curr);
}

curr=s.top();
s.pop();
while(!s.empty() and curr==s.top() ){
    s.pop();
    curr++;
}
s.push(curr);

//cerr<<"nakraq, bez da pravq nishto ima "<<s.size()<<" elementi s nai-goren"<<s.top()<<endl;
if(s.size()>1){

    while(!s.empty()){
        curr=s.top();
        s.pop();

        //cerr<<"sega otgore stoeshe "<<curr<<" i she gi butam nadolu"<<endl;
        while(!s.empty() and curr==s.top() ){
            s.pop();
            curr++;
        }

        if(!s.empty()){
            //cerr<<"nai-otgore ima "<<s.top()<<" i she dobavq oshte 1"<<endl;
            added.pb({s.top(), n-1});
        }
    }
}
//cerr<<s.size()<<endl;
//cerr<<"added: "<<added.size()<<endl;

queue<pii> q;
if(added.size()<=k){

    for(auto i: added){
        q.push({i.first, i.second});
    }
    //cerr<<q.size()<<endl;

    while(q.size()<k){
        //cerr<<"pochnah da splitvam"<<endl;
        pii fr=q.front();
        q.pop();

        q.push({fr.first-1, fr.second});
        q.push({fr.first-1, fr.second});
    }
}

for(int i=0; i<n; i++){
    ans.pb({a[i], i});
}
while(!q.empty()){
    pii fr=q.front();
    q.pop();

    ans.pb(fr);
    //cerr<<"pushed "<<fr.first<<endl;
}

sort(ans.begin(), ans.end(), cmp);

for(auto i: ans){
    cout<<i.first<<" ";
}
cout<<endl;
return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:120:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 | if(added.size()<=k){
      |    ~~~~~~~~~~~~^~~
zalmoxis.cpp:127:19: warning: comparison of integer expressions of different signedness: 'std::queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |     while(q.size()<k){
      |           ~~~~~~~~^~

• Subtask 1: 0 / 30
• Subtask 2: 10 / 70