oj.uz

Submission #967271

# Submission time Handle Problem Language Result Execution time Memory
967271 2024-04-21T16:47:39 Z v_matei Mobile (BOI12_mobile) C++17
100 / 100
 956 ms 63932 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 INF 2e9
         
        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) {
          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() {
          std::ios::sync_with_stdio(0);
          std::cin.tie(0);
          std::cout.tie(0);
          citire();
          double k = b_search(0, INF, find_point);
          std::cout << std::fixed << std::setprecision(10) << k;
          return 0;
        }

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5636 KB Output is correct
2 Correct 61 ms 5768 KB Output is correct
3 Correct 36 ms 3588 KB Output is correct
4 Correct 31 ms 3128 KB Output is correct
5 Correct 16 ms 2272 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3092 KB Output is correct
2 Correct 26 ms 3284 KB Output is correct
3 Correct 35 ms 3524 KB Output is correct
4 Correct 32 ms 3212 KB Output is correct
5 Correct 37 ms 3728 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 5864 KB Output is correct
2 Correct 62 ms 5960 KB Output is correct
3 Correct 41 ms 4560 KB Output is correct
4 Correct 44 ms 4808 KB Output is correct
5 Correct 31 ms 3576 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6736 KB Output is correct
2 Correct 81 ms 7148 KB Output is correct
3 Correct 57 ms 6292 KB Output is correct
4 Correct 45 ms 5376 KB Output is correct
5 Correct 39 ms 4744 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 7244 KB Output is correct
2 Correct 73 ms 7212 KB Output is correct
3 Correct 62 ms 5980 KB Output is correct
4 Correct 46 ms 4776 KB Output is correct
5 Correct 38 ms 4068 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 26872 KB Output is correct
2 Correct 375 ms 28732 KB Output is correct
3 Correct 304 ms 31784 KB Output is correct
4 Correct 219 ms 24932 KB Output is correct
5 Correct 195 ms 22744 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 28876 KB Output is correct
2 Correct 360 ms 27912 KB Output is correct
3 Correct 274 ms 26440 KB Output is correct
4 Correct 214 ms 20420 KB Output is correct
5 Correct 195 ms 19816 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 40632 KB Output is correct
2 Correct 449 ms 40880 KB Output is correct
3 Correct 367 ms 46380 KB Output is correct
4 Correct 285 ms 30072 KB Output is correct
5 Correct 227 ms 25900 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 42184 KB Output is correct
2 Correct 435 ms 44304 KB Output is correct
3 Correct 339 ms 32740 KB Output is correct
4 Correct 265 ms 28988 KB Output is correct
5 Correct 252 ms 25392 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 43924 KB Output is correct
2 Correct 551 ms 45940 KB Output is correct
3 Correct 488 ms 49196 KB Output is correct
4 Correct 309 ms 32964 KB Output is correct
5 Correct 264 ms 29060 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 46452 KB Output is correct
2 Correct 482 ms 45340 KB Output is correct
3 Correct 392 ms 32204 KB Output is correct
4 Correct 305 ms 32684 KB Output is correct
5 Correct 295 ms 24556 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 49644 KB Output is correct
2 Correct 581 ms 48488 KB Output is correct
3 Correct 465 ms 54624 KB Output is correct
4 Correct 367 ms 42776 KB Output is correct
5 Correct 342 ms 40560 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 49016 KB Output is correct
2 Correct 554 ms 49104 KB Output is correct
3 Correct 403 ms 44716 KB Output is correct
4 Correct 370 ms 34408 KB Output is correct
5 Correct 314 ms 28612 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 53036 KB Output is correct
2 Correct 609 ms 63932 KB Output is correct
3 Correct 708 ms 62872 KB Output is correct
4 Correct 454 ms 51224 KB Output is correct
5 Correct 413 ms 44952 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 61112 KB Output is correct
2 Correct 685 ms 61400 KB Output is correct
3 Correct 564 ms 56800 KB Output is correct
4 Correct 460 ms 50864 KB Output is correct
5 Correct 406 ms 46332 KB Output is correct