oj.uz

Submission #668289

# Submission time Handle Problem Language Result Execution time Memory
668289 2022-12-03T14:54:58 Z MrDeboo Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 164 ms 35360 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
deque<int>dqqq;
int k;
void ss(int a){
    k++;
    deque<int>dq={a};
    while(dq.size()*2<=k){
        int x=dq.size();
        for(int i=0;i<x;i++){
            dq.push_back(dq[i]-1);
                dq.push_back(dq[i]-1);
        }
        for(int i=0;i<x;i++){
            dq.pop_front();
        }
    }
    int c=dq.size()*2-k;
    for(int i=0;i<c;i++){
        k--;
        dqqq.push_back(dq[i]);
    }
    for(int i=c;i<dq.size();i++){
        k--;k--;
        dqqq.push_back(dq[i]-1);
            dqqq.push_back(dq[i]-1);
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n>>k;
    deque<int>a,b(n);
    for(auto &i:b)cin>>i;
    deque<int>doq=b;
    deque<int>dq={b[0]};
    deque<int>dqq={1};
    a.push_back(b[0]);
    b.pop_front();
    while(b.size()){
        if(b[0]<=a.back()){
            a.push_back(b[0]);
            dq.push_back(b[0]);
            dqq.push_back(1);
            b.pop_front();
        }else{
            k--;
            a.push_back(a.back());
            dq.push_back(a.back());
            dqq.push_back(0);
        }
        while(a.size()>1&&a.back()==a[a.size()-2]){
            int A=a.back();
            a.pop_back();
            a.pop_back();
            a.push_back(A+1);
        }
    }
    while(a.size()>1){
        a.push_back(a.back());
        dq.push_back(a.back());
        dqq.push_back(0);
        k--;
        while(a.size()>1&&a.back()==a[a.size()-2]){
            int A=a.back();
            a.pop_back();
            a.pop_back();
            a.push_back(A+1);
        }
    }
    int g=a.back();
    if(g==30){
        if(k==0){for(auto &i:dq)cout<<i<<' ';return 0;}
        for(int i=0;i<dq.size();i++){
            if(dqq[i])dqqq.push_back(dq[i]);
            else{
                ss(dq[i]);
            }
        }
        for(auto &i:dqqq)cout<<i<<' ';
    }
    else{
        for(int i=g;i<=29&&k;i++){
            dq.push_back(i);
            k--;
        }
        int z=dq.back();
        dq.pop_back();
        k++;
        deque<int>dqq={z};
        while(dqq.size()*2<=k){
            int x=dqq.size();
            for(int i=0;i<x;i++){
                dqq.push_back(dqq[i]-1);
                    dqq.push_back(dqq[i]-1);
            }
            for(int i=0;i<x;i++){
                dqq.pop_front();
            }
        }
        int c=dqq.size()*2-k;
        for(int i=0;i<c;i++){
            k--;
            dq.push_back(dqq[i]);
        }
        for(int i=c;i<dqq.size();i++){
            k--;k--;
            dq.push_back(dqq[i]-1);
                dq.push_back(dqq[i]-1);
        }
        assert(k==0);
        for(auto &i:dq)cout<<i<<' ';
    }
}

Compilation message

zalmoxis.cpp: In function 'void ss(long long int)':
zalmoxis.cpp:14:22: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   14 |     while(dq.size()*2<=k){
      |           ~~~~~~~~~~~^~~
zalmoxis.cpp:29:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=c;i<dq.size();i++){
      |                 ~^~~~~~~~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:80:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i=0;i<dq.size();i++){
      |                     ~^~~~~~~~~~
zalmoxis.cpp:97:27: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   97 |         while(dqq.size()*2<=k){
      |               ~~~~~~~~~~~~^~~
zalmoxis.cpp:112:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int i=c;i<dqq.size();i++){
      |                     ~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 27084 KB Output is correct
2 Correct 139 ms 27048 KB Output is correct
3 Correct 138 ms 27072 KB Output is correct
4 Correct 138 ms 27092 KB Output is correct
5 Correct 140 ms 27108 KB Output is correct
6 Correct 143 ms 27084 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 35300 KB Output is correct
2 Correct 164 ms 27096 KB Output is correct
3 Correct 159 ms 35248 KB Output is correct
4 Correct 148 ms 35308 KB Output is correct
5 Correct 153 ms 35276 KB Output is correct
6 Correct 156 ms 35308 KB Output is correct
7 Correct 145 ms 35360 KB Output is correct
8 Correct 149 ms 35272 KB Output is correct
9 Correct 150 ms 32616 KB Output is correct
10 Correct 97 ms 21424 KB Output is correct
11 Correct 132 ms 25860 KB Output is correct
12 Correct 67 ms 14888 KB Output is correct
13 Correct 83 ms 14884 KB Output is correct
14 Correct 79 ms 14852 KB Output is correct