oj.uz

Submission #432334

# Submission time Handle Problem Language Result Execution time Memory
432334 2021-06-18T08:12:16 Z four_specks Mobile (BOI12_mobile) C++17
100 / 100
 777 ms 31712 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 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 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 3 ms 332 KB Output is correct
2 Correct 3 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 400 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 4 ms 440 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 4 ms 460 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 492 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
5 Correct 4 ms 412 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2636 KB Output is correct
2 Correct 56 ms 2556 KB Output is correct
3 Correct 29 ms 1992 KB Output is correct
4 Correct 42 ms 1868 KB Output is correct
5 Correct 26 ms 1484 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2192 KB Output is correct
2 Correct 45 ms 2216 KB Output is correct
3 Correct 48 ms 2636 KB Output is correct
4 Correct 44 ms 2076 KB Output is correct
5 Correct 46 ms 1868 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3052 KB Output is correct
2 Correct 64 ms 2636 KB Output is correct
3 Correct 45 ms 2928 KB Output is correct
4 Correct 54 ms 1904 KB Output is correct
5 Correct 55 ms 2500 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2756 KB Output is correct
2 Correct 72 ms 2884 KB Output is correct
3 Correct 54 ms 3432 KB Output is correct
4 Correct 46 ms 1896 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 69 ms 3412 KB Output is correct
2 Correct 67 ms 2916 KB Output is correct
3 Correct 54 ms 3460 KB Output is correct
4 Correct 53 ms 2116 KB Output is correct
5 Correct 60 ms 3044 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 15948 KB Output is correct
2 Correct 331 ms 8916 KB Output is correct
3 Correct 359 ms 8904 KB Output is correct
4 Correct 233 ms 8540 KB Output is correct
5 Correct 318 ms 11336 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 8912 KB Output is correct
2 Correct 416 ms 15940 KB Output is correct
3 Correct 272 ms 16060 KB Output is correct
4 Correct 245 ms 8520 KB Output is correct
5 Correct 289 ms 10060 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 19096 KB Output is correct
2 Correct 396 ms 10464 KB Output is correct
3 Correct 385 ms 10564 KB Output is correct
4 Correct 288 ms 9980 KB Output is correct
5 Correct 402 ms 13808 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 10472 KB Output is correct
2 Correct 477 ms 19040 KB Output is correct
3 Correct 324 ms 19060 KB Output is correct
4 Correct 281 ms 10052 KB Output is correct
5 Correct 345 ms 11972 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 22212 KB Output is correct
2 Correct 472 ms 12040 KB Output is correct
3 Correct 457 ms 12100 KB Output is correct
4 Correct 334 ms 11644 KB Output is correct
5 Correct 468 ms 16128 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 12048 KB Output is correct
2 Correct 548 ms 22212 KB Output is correct
3 Correct 387 ms 22216 KB Output is correct
4 Correct 330 ms 11648 KB Output is correct
5 Correct 426 ms 13820 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 25304 KB Output is correct
2 Correct 524 ms 13636 KB Output is correct
3 Correct 564 ms 13636 KB Output is correct
4 Correct 386 ms 13252 KB Output is correct
5 Correct 504 ms 16668 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 13600 KB Output is correct
2 Correct 604 ms 25328 KB Output is correct
3 Correct 466 ms 25292 KB Output is correct
4 Correct 420 ms 13252 KB Output is correct
5 Correct 469 ms 15644 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 31572 KB Output is correct
2 Correct 644 ms 16728 KB Output is correct
3 Correct 627 ms 16856 KB Output is correct
4 Correct 507 ms 16528 KB Output is correct
5 Correct 630 ms 21188 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 16836 KB Output is correct
2 Correct 777 ms 31560 KB Output is correct
3 Correct 603 ms 31712 KB Output is correct
4 Correct 481 ms 16484 KB Output is correct
5 Correct 594 ms 18908 KB Output is correct