oj.uz

Submission #750168

# Submission time Handle Problem Language Result Execution time Memory
750168 2023-05-29T07:26:16 Z MrM7md Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 252 ms 77972 KB 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=1e6+500;
const int off=(1<<18);
const int MOD = 1e9+7;


vector<vector<int>>kk(N),ans(N);
signed main(){
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int n,k;
   cin >> n >> k;
   vector<pair<int,int>> a(n);
   for(int i=0;i<n;i++){
      cin >> a[i].F;
      a[i].S=i;
   }
   vector<pair<int,int>>v=a;
   for(int i=0;i<=29;i++){
      vector<pair<int,int>>t;
      for(int j=0;j<v.size();j++){
         if(j+1<v.size()&&v[j].F==v[j+1].F&&v[j].F==i){
            t.pb({v[j].F+1,v[j+1].S});

            j++;
         }
         else if(v[j].F==i){
            t.pb({v[j].F+1,v[j].S});
            kk[v[j].S].pb(v[j].F);
            k--;
         }
         else{
            t.pb(v[j]);
         }
      }
      v=t;
   }
   for(int i=0;i<n;i++){
      while(!kk[i].empty()&&k>0){
         int x=kk[i].back();
         if(x==0){
            ans[i].pb(x);
            kk[i].pop_back();
            continue;
         }
         k--;
         kk[i].pop_back();
         kk[i].pb(x-1),kk[i].pb(x-1);
      }
      // reverse(all(kk[i]));
      while(!kk[i].empty()&&k==0){
         ans[i].pb(kk[i].back());
         kk[i].pop_back();
      }
      reverse(all(ans[i]));
   }

   for(int i=0;i<n;i++){
      cout<<a[i].F<<' ';
      for(auto it:ans[i])cout<<it<<' ';
   }
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |       for(int j=0;j<v.size();j++){
      |                   ~^~~~~~~~~
zalmoxis.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |          if(j+1<v.size()&&v[j].F==v[j+1].F&&v[j].F==i){
      |             ~~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 77544 KB Output is correct
2 Correct 211 ms 77820 KB Output is correct
3 Correct 234 ms 77620 KB Output is correct
4 Correct 235 ms 77716 KB Output is correct
5 Correct 225 ms 77728 KB Output is correct
6 Correct 205 ms 77352 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 77608 KB Output is correct
2 Correct 202 ms 77380 KB Output is correct
3 Correct 252 ms 77776 KB Output is correct
4 Correct 237 ms 77900 KB Output is correct
5 Correct 224 ms 77708 KB Output is correct
6 Correct 214 ms 77612 KB Output is correct
7 Correct 230 ms 77780 KB Output is correct
8 Correct 222 ms 77972 KB Output is correct
9 Correct 220 ms 75856 KB Output is correct
10 Correct 161 ms 62124 KB Output is correct
11 Correct 175 ms 65672 KB Output is correct
12 Correct 102 ms 53316 KB Output is correct
13 Correct 101 ms 53308 KB Output is correct
14 Correct 101 ms 53308 KB Output is correct