oj.uz

Submission #863470

# Submission time Handle Problem Language Result Execution time Memory
863470 2023-10-20T12:16:32 Z bane Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 204 ms 90504 KB 
/* DK ORZ! */
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "algorithm"
#include "cmath"
#include "vector"
#include "set"
#include "map"
#include "unordered_set"
#include "unordered_map"
#include "queue"
#include "ctime"
#include "random"
#include "cassert"
#include "complex"
#include "string"
#include "cstring"
#include "chrono"
#include "bitset"
#include "array"
#include "stack"

#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long

using namespace std;

const int mod = 998244353;


void solve(){
  int n, k;
  cin >> n >> k;
  vector <pair<int,int>> a;
  for (int i = 0; i < n; i++){
    int x; cin >> x; a.push_back({x,i});
  }
  auto orig = a;
  vector <int> add[n];

  for (int i = 0; i < 30; i++){
    vector <pair<int,int>>b;
    for (int j = 0; j < (int)a.size(); j++){
      if (a[j].first != i){
        b.push_back(a[j]);
        continue;
      }
      if (j + 1 < (int)a.size()){
        if (a[j + 1].first == i){
          b.push_back({i + 1, a[j + 1].second});
          ++j;
          continue;
        }
        add[a[j].second].push_back(i);
        b.push_back({i+1,a[j].second});
        --k;
        continue;
      }
      add[a[j].second].push_back(i);
      b.push_back({i+1,a[j].second});
      --k;
    }
    a = b;
  }
  
  for (int i = 0; i < n; i++){
    cout << orig[i].first << " ";
    for (int j : add[i]){
      deque <int> other;
      other.push_back(j);
      while(other.size() > 0){
        int x = other.front();
        if (x > 0 && k > 0){
          other.pop_front();
          other.push_front(x-1);
          other.push_front(x-1);
          --k;
          continue;
        }
        cout << x << " ";
        other.pop_front();
      }
    }
  }
  
  cout << endl;
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt = 1;
//  cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 86848 KB Output is correct
2 Correct 170 ms 87892 KB Output is correct
3 Correct 204 ms 86744 KB Output is correct
4 Correct 172 ms 87384 KB Output is correct
5 Correct 173 ms 88384 KB Output is correct
6 Correct 165 ms 87956 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 87344 KB Output is correct
2 Correct 178 ms 86904 KB Output is correct
3 Correct 175 ms 88932 KB Output is correct
4 Correct 174 ms 88120 KB Output is correct
5 Correct 177 ms 87952 KB Output is correct
6 Correct 170 ms 90504 KB Output is correct
7 Correct 171 ms 87876 KB Output is correct
8 Correct 180 ms 89280 KB Output is correct
9 Correct 163 ms 75812 KB Output is correct
10 Correct 109 ms 33220 KB Output is correct
11 Correct 155 ms 47372 KB Output is correct
12 Correct 56 ms 2408 KB Output is correct
13 Correct 58 ms 2240 KB Output is correct
14 Correct 56 ms 2384 KB Output is correct