Submission #647723

#	Time	Username	Problem	Language	Result	Execution time	Memory
647723		tvladm2009	Zalmoxis (BOI18_zalmoxis)	C++14	35 / 100	157 ms	14376 KiB

zalmoxis

#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 (stderr)

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