oj.uz

Submission #837890

# Submission time Handle Problem Language Result Execution time Memory
837890 2023-08-25T19:39:19 Z teo_thrash Zalmoxis (BOI18_zalmoxis) C++14
10 / 100
 273 ms 20528 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 16292 KB Unexpected end of file - int32 expected
2 Incorrect 154 ms 16272 KB Unexpected end of file - int32 expected
3 Incorrect 154 ms 16300 KB Unexpected end of file - int32 expected
4 Incorrect 161 ms 16300 KB Unexpected end of file - int32 expected
5 Incorrect 159 ms 16296 KB Unexpected end of file - int32 expected
6 Incorrect 155 ms 16172 KB Unexpected end of file - int32 expected

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 16316 KB not a zalsequence
2 Correct 191 ms 16308 KB Output is correct
3 Correct 264 ms 16332 KB Output is correct
4 Incorrect 190 ms 16368 KB not a zalsequence
5 Incorrect 158 ms 16296 KB not a zalsequence
6 Incorrect 273 ms 16356 KB not a zalsequence
7 Incorrect 256 ms 16432 KB not a zalsequence
8 Incorrect 159 ms 16372 KB not a zalsequence
9 Incorrect 173 ms 17824 KB not a zalsequence
10 Incorrect 163 ms 19096 KB not a zalsequence
11 Incorrect 168 ms 18736 KB not a zalsequence
12 Incorrect 127 ms 20400 KB not a zalsequence
13 Incorrect 111 ms 20240 KB not a zalsequence
14 Incorrect 111 ms 20528 KB not a zalsequence