Submission #863470

#	Time	Username	Problem	Language	Result	Execution time	Memory
863470		bane	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	204 ms	90504 KiB

zalmoxis

/* 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 / 30
• Subtask 2: 70 / 70