oj.uz

Submission #647721

# Submission time Handle Problem Language Result Execution time Memory
647721 2022-10-03T20:33:56 Z tvladm2009 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 188 ms 262144 KB 
#include <bits/stdc++.h>

using ll = long long;

int const nmax = 1000000;

int v[1 + 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, w - 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 167 ms 14184 KB Output is correct
2 Correct 137 ms 14248 KB Output is correct
3 Correct 156 ms 14244 KB Output is correct
4 Correct 136 ms 14256 KB Output is correct
5 Correct 138 ms 14252 KB Output is correct
6 Correct 137 ms 14144 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 175 ms 262144 KB Execution killed with signal 9
2 Correct 156 ms 14168 KB Output is correct
3 Incorrect 133 ms 14196 KB Unexpected end of file - int32 expected
4 Runtime error 169 ms 262144 KB Execution killed with signal 9
5 Runtime error 188 ms 262144 KB Execution killed with signal 9
6 Runtime error 176 ms 262144 KB Execution killed with signal 9
7 Runtime error 170 ms 262144 KB Execution killed with signal 9
8 Runtime error 187 ms 262144 KB Execution killed with signal 9
9 Runtime error 175 ms 262144 KB Execution killed with signal 9
10 Runtime error 156 ms 262144 KB Execution killed with signal 9
11 Runtime error 143 ms 262144 KB Execution killed with signal 9
12 Runtime error 124 ms 262144 KB Execution killed with signal 9
13 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
14 Runtime error 117 ms 262144 KB Execution killed with signal 9