oj.uz

Submission #647723

# Submission time Handle Problem Language Result Execution time Memory
647723 2022-10-03T20:40:30 Z tvladm2009 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 157 ms 14376 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 143 ms 14244 KB Output is correct
2 Correct 138 ms 14188 KB Output is correct
3 Correct 134 ms 14180 KB Output is correct
4 Correct 152 ms 14208 KB Output is correct
5 Correct 139 ms 14312 KB Output is correct
6 Correct 135 ms 14252 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 14228 KB Expected EOF
2 Correct 153 ms 14276 KB Output is correct
3 Incorrect 137 ms 14276 KB Unexpected end of file - int32 expected
4 Incorrect 143 ms 14272 KB Expected EOF
5 Incorrect 146 ms 14296 KB Expected EOF
6 Incorrect 142 ms 14228 KB Expected EOF
7 Incorrect 141 ms 14376 KB Expected EOF
8 Incorrect 157 ms 14236 KB Expected EOF
9 Incorrect 137 ms 12884 KB Unexpected end of file - int32 expected
10 Incorrect 57 ms 5832 KB Unexpected end of file - int32 expected
11 Incorrect 87 ms 10632 KB Unexpected end of file - int32 expected
12 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
13 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
14 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected