oj.uz

Submission #1053595

# Submission time Handle Problem Language Result Execution time Memory
1053595 2024-08-11T14:09:15 Z vjudge1 Measures (CEOI22_measures) C++17
24 / 100
 1500 ms 6504 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's not the baby, that's my baby
#define int ll

#define debug(x) #x << " = " << x << '\n'
typedef long long ll;

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif
  
  int n, m, D;
  std::cin >> n >> m >> D;
  D *= 2;

  std::vector<int> a;
  if (n != 0) {
    a.resize(n);
    for (auto &x : a) {
      std::cin >> x;
      x *= 2;
    }
  }

  auto check = [&](int mid) {
    ll last = -8e18;
    for (const auto &x : a) {
      if (last + D <= x) {
        last = std::max(last + D, (ll) x - mid);
      } else {
        if (x + mid < last + D) {
          return false;
        }
        last += D;
      }
    }
    return true;
  };

  while (m--) {
    int x;
    std::cin >> x;
    a.push_back(2 * x);
    std::sort(a.begin(), a.end());
    int l = 0, r = 1e18;
    while (l < r) {
      int mid = (l + r) / 2;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    std::cout << r / 2;
    if (r % 2) {
      std::cout << ".5";
    }
    std::cout << ' ';
  }

  return 0;
}

Compilation message

Main.cpp:5:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    5 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 178 ms 6504 KB Output is correct
10 Correct 206 ms 6224 KB Output is correct
11 Correct 131 ms 6488 KB Output is correct
12 Correct 225 ms 5464 KB Output is correct
13 Correct 127 ms 5872 KB Output is correct
14 Correct 165 ms 5468 KB Output is correct
15 Correct 166 ms 5724 KB Output is correct
16 Correct 129 ms 6492 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 592 KB Time limit exceeded
2 Halted 0 ms 0 KB -