oj.uz

Submission #1063747

# Submission time Handle Problem Language Result Execution time Memory
1063747 2024-08-18T00:59:48 Z daviedu Mobile (BOI12_mobile) C++17
90 / 100
 1000 ms 51072 KB 
#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define ld long double

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const ld prec = 0.0001;
const ld MX = 1e10;
vector<pair<ld, ld>> points;
int n, len;

bool f(ld r){
    ld right=0;
    for (auto& [x, y]: points){
        if (r < y) continue;
        ld dx = sqrtl(r*r - y*y);
        if (x-dx <= right) right = max(right, x+dx);
    }
    return right >= len;
}

signed main(){
    fastio;
    cin >> n >> len;
    points.resize(n);
    for (int i=0; i<n; i++){
        cin >> points[i].first;
        cin >> points[i].second;
    }
    
    ld l=0, r=MX, ans=MX;
    while (r-l >= prec){
        ld m = (l+r)/2;
        if (f(m)) r = m, ans = m;
        else l = m;
    }
    cout << fixed << setprecision(13);
    cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2652 KB Output is correct
2 Correct 40 ms 2652 KB Output is correct
3 Correct 36 ms 2524 KB Output is correct
4 Correct 81 ms 3920 KB Output is correct
5 Correct 31 ms 2396 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2908 KB Output is correct
2 Correct 57 ms 3416 KB Output is correct
3 Correct 69 ms 3928 KB Output is correct
4 Correct 75 ms 4084 KB Output is correct
5 Correct 88 ms 4440 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3160 KB Output is correct
2 Correct 43 ms 4180 KB Output is correct
3 Correct 41 ms 3932 KB Output is correct
4 Correct 98 ms 5468 KB Output is correct
5 Correct 65 ms 4188 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3416 KB Output is correct
2 Correct 54 ms 4952 KB Output is correct
3 Correct 55 ms 4444 KB Output is correct
4 Correct 99 ms 5712 KB Output is correct
5 Correct 91 ms 4740 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3420 KB Output is correct
2 Correct 53 ms 3420 KB Output is correct
3 Correct 58 ms 4476 KB Output is correct
4 Correct 100 ms 5456 KB Output is correct
5 Correct 89 ms 4700 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 15964 KB Output is correct
2 Correct 262 ms 23632 KB Output is correct
3 Correct 270 ms 23124 KB Output is correct
4 Correct 501 ms 25584 KB Output is correct
5 Correct 432 ms 22864 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 15964 KB Output is correct
2 Correct 317 ms 22864 KB Output is correct
3 Correct 254 ms 21744 KB Output is correct
4 Correct 507 ms 25424 KB Output is correct
5 Correct 451 ms 23376 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 19032 KB Output is correct
2 Correct 317 ms 28496 KB Output is correct
3 Correct 319 ms 27808 KB Output is correct
4 Correct 637 ms 31020 KB Output is correct
5 Correct 537 ms 27216 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 19036 KB Output is correct
2 Correct 354 ms 27168 KB Output is correct
3 Correct 304 ms 25940 KB Output is correct
4 Correct 616 ms 30800 KB Output is correct
5 Correct 571 ms 27732 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 22364 KB Output is correct
2 Correct 407 ms 33108 KB Output is correct
3 Correct 396 ms 32340 KB Output is correct
4 Correct 723 ms 35668 KB Output is correct
5 Correct 609 ms 31312 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 22360 KB Output is correct
2 Correct 402 ms 31460 KB Output is correct
3 Correct 338 ms 30544 KB Output is correct
4 Correct 700 ms 35664 KB Output is correct
5 Correct 634 ms 32336 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 25436 KB Output is correct
2 Correct 439 ms 37716 KB Output is correct
3 Correct 458 ms 36944 KB Output is correct
4 Correct 831 ms 41044 KB Output is correct
5 Correct 739 ms 36432 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 25436 KB Output is correct
2 Correct 462 ms 35988 KB Output is correct
3 Correct 406 ms 34948 KB Output is correct
4 Correct 827 ms 40784 KB Output is correct
5 Correct 724 ms 36944 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 31580 KB Output is correct
2 Correct 552 ms 47184 KB Output is correct
3 Correct 516 ms 46164 KB Output is correct
4 Execution timed out 1014 ms 50768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 31836 KB Output is correct
2 Correct 568 ms 44884 KB Output is correct
3 Correct 474 ms 43860 KB Output is correct
4 Execution timed out 1032 ms 51072 KB Time limit exceeded
5 Halted 0 ms 0 KB -