oj.uz

Submission #432337

# Submission time Handle Problem Language Result Execution time Memory
432337 2021-06-18T08:14:43 Z four_specks Mobile (BOI12_mobile) C++17
100 / 100
 760 ms 31684 KB 
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    struct point
    {
        long x, y;
    };

    int n;
    long l;
    cin >> n >> l;

    vector<point> coords(n);
    for (int i = 0; i < n; i++)
        cin >> coords[i].x >> coords[i].y;

    auto valid = [&](const double &d) -> bool
    {
        vector<pair<double, double>> cov;
        cov.reserve(2 * n);
        for (const auto &[x, y] : coords)
        {
            if (y * y < d * d)
            {
                double h = sqrt(d * d - y * y);
                while (!cov.empty() && cov.back().first > x - h)
                    cov.pop_back();
                cov.emplace_back(x - h, x + h);
            }
        }

        bool ended = 0;
        double e = 0.0;
        for (const auto &[x1, x2] : cov)
        {
            if (x1 <= e)
            {
                if (e = max(e, x2); e >= l)
                {
                    ended = 1;
                    break;
                }
            }
            else
                break;
        }

        return ended;
    };

    double ans = 3e9;
    for (double lo = 0.5; ans - lo > 1e-5;)
    {
        if (double mid = (lo + ans) / 2.0; valid(mid))
            ans = mid;
        else
            lo = mid + 1e-4;
    }

    cout << fixed << setprecision(5) << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2640 KB Output is correct
2 Correct 51 ms 2556 KB Output is correct
3 Correct 29 ms 1996 KB Output is correct
4 Correct 43 ms 1868 KB Output is correct
5 Correct 25 ms 1484 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2172 KB Output is correct
2 Correct 45 ms 2196 KB Output is correct
3 Correct 50 ms 2620 KB Output is correct
4 Correct 49 ms 1940 KB Output is correct
5 Correct 45 ms 1868 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3052 KB Output is correct
2 Correct 59 ms 2636 KB Output is correct
3 Correct 44 ms 2976 KB Output is correct
4 Correct 46 ms 1876 KB Output is correct
5 Correct 57 ms 2496 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2764 KB Output is correct
2 Correct 67 ms 2884 KB Output is correct
3 Correct 53 ms 3404 KB Output is correct
4 Correct 46 ms 1912 KB Output is correct
5 Correct 60 ms 3140 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3428 KB Output is correct
2 Correct 75 ms 2912 KB Output is correct
3 Correct 53 ms 3396 KB Output is correct
4 Correct 47 ms 1964 KB Output is correct
5 Correct 60 ms 3040 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 15944 KB Output is correct
2 Correct 322 ms 8916 KB Output is correct
3 Correct 339 ms 8900 KB Output is correct
4 Correct 228 ms 8416 KB Output is correct
5 Correct 303 ms 11332 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 8916 KB Output is correct
2 Correct 399 ms 15960 KB Output is correct
3 Correct 282 ms 15904 KB Output is correct
4 Correct 236 ms 8532 KB Output is correct
5 Correct 291 ms 10056 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 19092 KB Output is correct
2 Correct 399 ms 10436 KB Output is correct
3 Correct 383 ms 10464 KB Output is correct
4 Correct 281 ms 9996 KB Output is correct
5 Correct 398 ms 13792 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 10468 KB Output is correct
2 Correct 481 ms 19044 KB Output is correct
3 Correct 363 ms 19052 KB Output is correct
4 Correct 283 ms 10004 KB Output is correct
5 Correct 366 ms 11872 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 22216 KB Output is correct
2 Correct 457 ms 12048 KB Output is correct
3 Correct 450 ms 12044 KB Output is correct
4 Correct 341 ms 11660 KB Output is correct
5 Correct 438 ms 16128 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 12028 KB Output is correct
2 Correct 570 ms 22212 KB Output is correct
3 Correct 383 ms 22212 KB Output is correct
4 Correct 336 ms 11680 KB Output is correct
5 Correct 416 ms 13824 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 25352 KB Output is correct
2 Correct 496 ms 13600 KB Output is correct
3 Correct 512 ms 13596 KB Output is correct
4 Correct 389 ms 13216 KB Output is correct
5 Correct 512 ms 16708 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 13600 KB Output is correct
2 Correct 592 ms 25300 KB Output is correct
3 Correct 443 ms 25288 KB Output is correct
4 Correct 376 ms 13216 KB Output is correct
5 Correct 457 ms 15648 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 31556 KB Output is correct
2 Correct 616 ms 16728 KB Output is correct
3 Correct 607 ms 16860 KB Output is correct
4 Correct 496 ms 16472 KB Output is correct
5 Correct 621 ms 21228 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 16740 KB Output is correct
2 Correct 760 ms 31684 KB Output is correct
3 Correct 574 ms 31584 KB Output is correct
4 Correct 466 ms 16488 KB Output is correct
5 Correct 569 ms 18920 KB Output is correct