oj.uz

Submission #729573

# Submission time Handle Problem Language Result Execution time Memory
729573 2023-04-24T09:16:28 Z PanosPask Mobile (BOI12_mobile) C++14
90 / 100
 1000 ms 35300 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long > pl;

int n, l;
vector<pl> transmitters;

bool distance_covers(double x)
{
    double latest_cover = 0;
    for (int i = 0; i < n && latest_cover < l; i++) {
        pl cur = transmitters[i];
        if (cur.second > x)
            continue;

        double k = sqrt(x * x - cur.second * cur.second);

        if (cur.first - k <= latest_cover)
            latest_cover = max(latest_cover, cur.first + k);
    }

    return latest_cover >= l;
}

int main(void)
{
    scanf("%d %d", &n, &l);
    transmitters.resize(n);
    for (int i = 0; i < n; i++)
        scanf("%lld %lld", &transmitters[i].first, &transmitters[i].second);

    double l = 0; //distance_covers(l) = false
    double r = 1; //distance_covers(r) = true
    while (!distance_covers(r)) {
        l = r;
        r *= 2;
    }

    for (int i = 0; i < 60; i++) {
        double mid = (l + r) / 2;
        if (distance_covers(mid))
            r = mid;
        else
            l = mid;
    }

    printf("%lf\n", r);
    return 0;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &n, &l);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mobile.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld %lld", &transmitters[i].first, &transmitters[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 6 ms 452 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1460 KB Output is correct
2 Correct 34 ms 2516 KB Output is correct
3 Correct 18 ms 1748 KB Output is correct
4 Correct 82 ms 2644 KB Output is correct
5 Correct 18 ms 1464 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1492 KB Output is correct
2 Correct 62 ms 2212 KB Output is correct
3 Correct 74 ms 2516 KB Output is correct
4 Correct 85 ms 2736 KB Output is correct
5 Correct 98 ms 3148 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1692 KB Output is correct
2 Correct 27 ms 1620 KB Output is correct
3 Correct 28 ms 1620 KB Output is correct
4 Correct 106 ms 1848 KB Output is correct
5 Correct 71 ms 2612 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1748 KB Output is correct
2 Correct 34 ms 1748 KB Output is correct
3 Correct 33 ms 1880 KB Output is correct
4 Correct 119 ms 1852 KB Output is correct
5 Correct 98 ms 3116 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1856 KB Output is correct
2 Correct 41 ms 1864 KB Output is correct
3 Correct 31 ms 1748 KB Output is correct
4 Correct 107 ms 1876 KB Output is correct
5 Correct 89 ms 3172 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 8120 KB Output is correct
2 Correct 169 ms 8120 KB Output is correct
3 Correct 152 ms 8124 KB Output is correct
4 Correct 526 ms 8124 KB Output is correct
5 Correct 467 ms 14952 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 8120 KB Output is correct
2 Correct 381 ms 8116 KB Output is correct
3 Correct 171 ms 13864 KB Output is correct
4 Correct 534 ms 17468 KB Output is correct
5 Correct 479 ms 15428 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 9684 KB Output is correct
2 Correct 208 ms 9684 KB Output is correct
3 Correct 200 ms 9688 KB Output is correct
4 Correct 649 ms 9684 KB Output is correct
5 Correct 536 ms 17608 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 9804 KB Output is correct
2 Correct 397 ms 9684 KB Output is correct
3 Correct 216 ms 16464 KB Output is correct
4 Correct 620 ms 21420 KB Output is correct
5 Correct 570 ms 18424 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 11248 KB Output is correct
2 Correct 267 ms 11252 KB Output is correct
3 Correct 229 ms 11260 KB Output is correct
4 Correct 736 ms 11248 KB Output is correct
5 Correct 599 ms 20292 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 11340 KB Output is correct
2 Correct 444 ms 11252 KB Output is correct
3 Correct 248 ms 19692 KB Output is correct
4 Correct 718 ms 24648 KB Output is correct
5 Correct 630 ms 21392 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 12812 KB Output is correct
2 Correct 302 ms 12756 KB Output is correct
3 Correct 279 ms 12816 KB Output is correct
4 Correct 895 ms 12816 KB Output is correct
5 Correct 767 ms 23984 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 12812 KB Output is correct
2 Correct 554 ms 12812 KB Output is correct
3 Correct 369 ms 22340 KB Output is correct
4 Correct 880 ms 28304 KB Output is correct
5 Correct 818 ms 24328 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 15956 KB Output is correct
2 Correct 377 ms 15960 KB Output is correct
3 Correct 329 ms 15956 KB Output is correct
4 Execution timed out 1058 ms 15956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 15952 KB Output is correct
2 Correct 727 ms 15956 KB Output is correct
3 Correct 394 ms 28224 KB Output is correct
4 Execution timed out 1053 ms 35300 KB Time limit exceeded
5 Halted 0 ms 0 KB -