oj.uz

Submission #967267

# Submission time Handle Problem Language Result Execution time Memory
967267 2024-04-21T16:40:19 Z v_matei Mobile (BOI12_mobile) C++17
60 / 100
 1000 ms 55284 KB 
#include <bits/stdc++.h>
#include <cmath>
#include <iomanip>

#define ll long long
#define ull unsigned long long
#define pdd std::pair<double, double>

#define NMAX 1e6
#define LMAX 1e9
#define INF 3e9

struct Tower {
  double x, y;
};
struct Seg {
  double st, fn;
};
double n, l;
std::vector<Tower> s;

void citire() {
  std::cin >> n >> l;
  s.resize(n);
  for (int i = 0; i < n; i++) {
    std::cin >> s[i].x >> s[i].y;
  }
}

double b_search(double lo, double hi, std::function<bool(double)> f) {
  // std::cout << "a\n";
  for (int i = 1; hi - lo > 0.001; i++) {
    double mid = (lo + hi) / 2;
    if (f(mid))
      hi = mid;
    else
      lo = mid;
  }
  return lo;
}

bool find_point(double k) {
  std::vector<Seg> segs;
  for (Tower &it : s) {
    if (k * k < it.y * it.y)
      continue;
    double max_dx = sqrt(k * k - it.y * it.y);
    segs.push_back({it.x - max_dx, it.x + max_dx});
    if (segs.back().st < 0 && segs.back().fn > l)
      return 1;
  }
  double pre = 0;
  for (Seg &it : segs) {
    if (pre >= l)
      return 1;
    if (pre >= it.st)
      pre = std::max(pre, it.fn);
  }
  return pre > l;
}

int main() {
  citire();
  // std::cout << "out\n";
  double k = b_search(0, INF, find_point);
  std::cout << std::setprecision(10) << k;
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 4 ms 604 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 796 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 5 ms 796 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 716 KB Output is correct
2 Correct 5 ms 796 KB Output is correct
3 Correct 4 ms 672 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 4848 KB Output is correct
2 Correct 94 ms 6080 KB Output is correct
3 Correct 56 ms 3580 KB Output is correct
4 Correct 62 ms 3736 KB Output is correct
5 Correct 30 ms 2364 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2532 KB Output is correct
2 Correct 51 ms 3232 KB Output is correct
3 Correct 61 ms 4048 KB Output is correct
4 Correct 67 ms 3608 KB Output is correct
5 Correct 74 ms 4704 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 5316 KB Output is correct
2 Correct 102 ms 6252 KB Output is correct
3 Correct 67 ms 4932 KB Output is correct
4 Correct 92 ms 5440 KB Output is correct
5 Correct 68 ms 4292 KB Output is correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 5708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5760 KB Output is correct
2 Correct 111 ms 7088 KB Output is correct
3 Correct 104 ms 6244 KB Output is correct
4 Correct 98 ms 5620 KB Output is correct
5 Correct 75 ms 4784 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 24312 KB Output is correct
2 Incorrect 616 ms 32528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 24660 KB Output is correct
2 Correct 564 ms 31056 KB Output is correct
3 Correct 442 ms 30648 KB Output is correct
4 Correct 458 ms 25096 KB Output is correct
5 Correct 398 ms 22328 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 36872 KB Output is correct
2 Incorrect 689 ms 46952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 718 ms 36784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 42208 KB Output is correct
2 Incorrect 857 ms 51676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 39140 KB Output is correct
2 Correct 782 ms 48860 KB Output is correct
3 Correct 639 ms 36060 KB Output is correct
4 Correct 657 ms 32744 KB Output is correct
5 Correct 558 ms 36176 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 43720 KB Output is correct
2 Incorrect 923 ms 55284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 42112 KB Output is correct
2 Correct 906 ms 53756 KB Output is correct
3 Correct 685 ms 48836 KB Output is correct
4 Correct 743 ms 41576 KB Output is correct
5 Correct 638 ms 39600 KB Output is correct

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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