oj.uz

Submission #656852

# Submission time Handle Problem Language Result Execution time Memory
656852 2022-11-08T10:50:43 Z MilosMilutinovic Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 180 ms 59244 KB 
#include <bits/stdc++.h>

using namespace std;

void Push(vector<int>& v) {
  while (v.size() >= 2) {
    int sz = (int) v.size();
    if (v[sz - 1] == v[sz - 2]) {
      int x = v[sz - 1];
      v.pop_back();
      v.pop_back();
      v.push_back(x + 1);
    } else {
      break;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  a.push_back(30);
  n++;
  vector<int> stk;
  vector<pair<int, int>> ans;
  for (int i = 0; i < n; i++) {
    while (!stk.empty() && stk.back() < a[i]) {
      int x = stk.back();
      ans.emplace_back(stk.back(), 1);
      stk.push_back(stk.back());
      Push(stk);
    }
    ans.emplace_back(a[i], 0);
    stk.push_back(a[i]);
    Push(stk);
  }
  ans.pop_back();
  for (auto& p : ans) {
    k -= p.second;
  }
  vector<int> res;
  function<void(int)> Add = [&](int x) {
    if (x == 1 || k == 0) {
      res.push_back(x);
    } else {
      k--;
      Add(x - 1);
      Add(x - 1);
    }
  };
  for (auto& p : ans) {
    if (p.second == 1) {
      Add(p.first);
    } else {
      res.push_back(p.first);
    }
  }
  for (auto& p : res) {
    cout << p << " ";
  }
  return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:34:11: warning: unused variable 'x' [-Wunused-variable]
   34 |       int x = stk.back();
      |           ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 22316 KB Output is correct
2 Correct 143 ms 22132 KB Output is correct
3 Correct 137 ms 22136 KB Output is correct
4 Correct 152 ms 22220 KB Output is correct
5 Correct 137 ms 22176 KB Output is correct
6 Correct 155 ms 22124 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 22240 KB Output is correct
2 Correct 180 ms 22076 KB Output is correct
3 Correct 153 ms 22080 KB Output is correct
4 Correct 154 ms 22140 KB Output is correct
5 Correct 133 ms 22144 KB Output is correct
6 Correct 144 ms 22076 KB Output is correct
7 Correct 137 ms 22296 KB Output is correct
8 Correct 134 ms 22176 KB Output is correct
9 Correct 128 ms 20912 KB Output is correct
10 Correct 138 ms 37084 KB Output is correct
11 Correct 113 ms 17420 KB Output is correct
12 Correct 108 ms 59244 KB Output is correct
13 Correct 113 ms 59176 KB Output is correct
14 Correct 76 ms 6284 KB Output is correct