oj.uz

Submission #729589

# Submission time Handle Problem Language Result Execution time Memory
729589 2023-04-24T09:25:42 Z PanosPask Mobile (BOI12_mobile) C++14
100 / 100
 828 ms 30724 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 < 40; 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 1 ms 256 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 212 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 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 308 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 340 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 5 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 37 ms 1748 KB Output is correct
2 Correct 27 ms 1748 KB Output is correct
3 Correct 15 ms 1484 KB Output is correct
4 Correct 64 ms 1816 KB Output is correct
5 Correct 15 ms 1332 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1768 KB Output is correct
2 Correct 46 ms 1748 KB Output is correct
3 Correct 55 ms 2036 KB Output is correct
4 Correct 67 ms 1876 KB Output is correct
5 Correct 71 ms 2004 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1876 KB Output is correct
2 Correct 25 ms 1848 KB Output is correct
3 Correct 24 ms 1788 KB Output is correct
4 Correct 85 ms 2004 KB Output is correct
5 Correct 50 ms 1976 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2108 KB Output is correct
2 Correct 35 ms 2048 KB Output is correct
3 Correct 27 ms 2048 KB Output is correct
4 Correct 87 ms 2004 KB Output is correct
5 Correct 69 ms 2224 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2112 KB Output is correct
2 Correct 31 ms 2004 KB Output is correct
3 Correct 28 ms 2028 KB Output is correct
4 Correct 90 ms 2068 KB Output is correct
5 Correct 70 ms 2224 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 8376 KB Output is correct
2 Correct 159 ms 8376 KB Output is correct
3 Correct 139 ms 8376 KB Output is correct
4 Correct 416 ms 8376 KB Output is correct
5 Correct 343 ms 8524 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 8376 KB Output is correct
2 Correct 259 ms 8372 KB Output is correct
3 Correct 146 ms 8536 KB Output is correct
4 Correct 404 ms 8644 KB Output is correct
5 Correct 375 ms 8560 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 9940 KB Output is correct
2 Correct 191 ms 9952 KB Output is correct
3 Correct 182 ms 9940 KB Output is correct
4 Correct 492 ms 9944 KB Output is correct
5 Correct 434 ms 10064 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 9940 KB Output is correct
2 Correct 324 ms 9876 KB Output is correct
3 Correct 185 ms 10032 KB Output is correct
4 Correct 491 ms 10348 KB Output is correct
5 Correct 433 ms 10156 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 11508 KB Output is correct
2 Correct 219 ms 11504 KB Output is correct
3 Correct 198 ms 11476 KB Output is correct
4 Correct 588 ms 11504 KB Output is correct
5 Correct 474 ms 11504 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 11624 KB Output is correct
2 Correct 339 ms 11508 KB Output is correct
3 Correct 189 ms 11468 KB Output is correct
4 Correct 559 ms 11764 KB Output is correct
5 Correct 486 ms 11772 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 13068 KB Output is correct
2 Correct 247 ms 13076 KB Output is correct
3 Correct 248 ms 13076 KB Output is correct
4 Correct 653 ms 13076 KB Output is correct
5 Correct 551 ms 13356 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 13260 KB Output is correct
2 Correct 376 ms 13072 KB Output is correct
3 Correct 233 ms 13164 KB Output is correct
4 Correct 657 ms 13404 KB Output is correct
5 Correct 566 ms 22512 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 16368 KB Output is correct
2 Correct 344 ms 16216 KB Output is correct
3 Correct 282 ms 16212 KB Output is correct
4 Correct 807 ms 16076 KB Output is correct
5 Correct 695 ms 29648 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 16340 KB Output is correct
2 Correct 432 ms 16360 KB Output is correct
3 Correct 287 ms 16120 KB Output is correct
4 Correct 828 ms 16408 KB Output is correct
5 Correct 721 ms 30724 KB Output is correct