oj.uz

Submission #668290

# Submission time Handle Problem Language Result Execution time Memory
668290 2022-12-03T14:56:15 Z MrDeboo Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 163 ms 35408 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&&dq.back()){
        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();
        }
    }
    if(!dq.back()){
        for(auto &i:dq){
            k--;
            dqqq.push_back(i);
        }
    }else{
        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&&dq.back()){
      |           ~~~~~~~~~~~^~~
zalmoxis.cpp:35: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]
   35 |         for(int i=c;i<dq.size();i++){
      |                     ~^~~~~~~~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:87: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]
   87 |         for(int i=0;i<dq.size();i++){
      |                     ~^~~~~~~~~~
zalmoxis.cpp:104: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]
  104 |         while(dqq.size()*2<=k){
      |               ~~~~~~~~~~~~^~~
zalmoxis.cpp:119: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]
  119 |         for(int i=c;i<dqq.size();i++){
      |                     ~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 27084 KB Output is correct
2 Correct 143 ms 27092 KB Output is correct
3 Correct 140 ms 27120 KB Output is correct
4 Correct 142 ms 27100 KB Output is correct
5 Correct 138 ms 27092 KB Output is correct
6 Correct 140 ms 27096 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 35288 KB Output is correct
2 Correct 142 ms 27104 KB Output is correct
3 Correct 152 ms 35308 KB Output is correct
4 Correct 151 ms 35284 KB Output is correct
5 Correct 150 ms 35408 KB Output is correct
6 Correct 151 ms 35316 KB Output is correct
7 Correct 163 ms 35356 KB Output is correct
8 Correct 148 ms 35308 KB Output is correct
9 Correct 148 ms 32500 KB Output is correct
10 Correct 94 ms 21344 KB Output is correct
11 Correct 130 ms 25544 KB Output is correct
12 Correct 67 ms 14816 KB Output is correct
13 Correct 69 ms 14860 KB Output is correct
14 Correct 72 ms 14816 KB Output is correct