oj.uz

Submission #647724

# Submission time Handle Problem Language Result Execution time Memory
647724 2022-10-03T21:00:49 Z tvladm2009 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 164 ms 14392 KB 
#include <bits/stdc++.h>

using ll = long long;

int const nmax = 1000000;

int v[5 + nmax];
std::vector<std::pair<int, int>> sol;
std::vector<int> st;

void normalize() {
  while(1 < st.size() && st[st.size() - 1] == st[st.size() - 2]) {
    st.pop_back();
    st.back()++;
  }
}

void print(int val, int w) {
  if(w == 1)
    std::cout << val << " ";
  else if(w <= (1 << (val - 1))) {
    print(val - 1, w - 1);
    print(val - 1, 1);
  } else {
    print(val - 1, (1 << (val - 1)));
    print(val - 1, w - (1 << (val - 1)));
  }
}

void repairsol(int n) {
  n = n - sol.size();
  for(int i = 0;i < sol.size(); i++) {
    if(sol[i].first == 0) {
      std::cout << sol[i].second << " ";
    } else {
      print(sol[i].second, std::min((1 << sol[i].second), n + 1));
      n -= std::min((1 << sol[i].second), n + 1) - 1;
    }
  }
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  int n, k;
  std::cin >> n >> k;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  v[n + 1] = 30;
  for(int i = 1;i <= n + 1; i++) {
    if(0 < st.size()) {
      while(st.back() < v[i]) {
        st.push_back(st.back());
        sol.push_back({1, st.back()});
        normalize();
      }
    }
    if(i <= n) {
      st.push_back(v[i]);
      sol.push_back({0, v[i]});
    }
    normalize();
  }
  repairsol(n + k);
  return 0;
}

Compilation message

zalmoxis.cpp: In function 'void repairsol(int)':
zalmoxis.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0;i < sol.size(); i++) {
      |                 ~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 14252 KB Output is correct
2 Correct 164 ms 14244 KB Output is correct
3 Correct 140 ms 14228 KB Output is correct
4 Correct 160 ms 14348 KB Output is correct
5 Correct 142 ms 14240 KB Output is correct
6 Correct 147 ms 14172 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 14316 KB Output is correct
2 Correct 134 ms 14248 KB Output is correct
3 Correct 134 ms 14220 KB Output is correct
4 Correct 163 ms 14300 KB Output is correct
5 Correct 140 ms 14392 KB Output is correct
6 Correct 137 ms 14272 KB Output is correct
7 Correct 131 ms 14284 KB Output is correct
8 Correct 147 ms 14272 KB Output is correct
9 Correct 125 ms 12960 KB Output is correct
10 Correct 93 ms 7052 KB Output is correct
11 Correct 107 ms 10568 KB Output is correct
12 Correct 79 ms 2272 KB Output is correct
13 Correct 95 ms 2252 KB Output is correct
14 Correct 85 ms 2208 KB Output is correct