oj.uz

Submission #1093734

# Submission time Handle Problem Language Result Execution time Memory
1093734 2024-09-27T10:52:21 Z michified Mobile (BOI12_mobile) C++17
50 / 100
 1000 ms 51284 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;

const ll mod = 1e9 + 7;

struct coord_t {
    ld x, y;
};

bool all(ld rad, ld l, vector<coord_t>& towers) {
    ld cur = 0, radsq = rad * rad;
    for (auto& t : towers) {
        if (t.y > rad) continue;
        ld horiz = sqrt(radsq - (t.y * t.y));
        if (t.x - horiz > cur) continue;
        cur = max(cur, t.x + horiz);
    }
    return cur >= l;
}

int main() {
    // ifstream cin("valleys.in");
    // ofstream cout("valleys.out");
    
    ld n, L, i, tx, ty;
    cin >> n >> L;
    vector<coord_t> towers(n);
    for (i = 0; i < n; i++) {
        cin >> tx >> ty;
        towers[i] = {tx, ty};
    }
    ld l = 0, r = 2e9, tol = 0.000001;
    while (l < r - tol) {
        ld mid = (l + r) / 2;
        if (not all(mid, L, towers)) l = mid;
        else r = mid - tol;
    }
    cout << setprecision(10) << l;
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 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 4 ms 600 KB Output is correct
2 Correct 6 ms 608 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 8 ms 692 KB Output is correct
5 Correct 5 ms 652 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3420 KB Output is correct
2 Correct 65 ms 3676 KB Output is correct
3 Correct 41 ms 2652 KB Output is correct
4 Correct 105 ms 3848 KB Output is correct
5 Correct 46 ms 2396 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3420 KB Output is correct
2 Correct 86 ms 3448 KB Output is correct
3 Correct 104 ms 3996 KB Output is correct
4 Correct 135 ms 4056 KB Output is correct
5 Correct 123 ms 4436 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 3860 KB Output is correct
2 Correct 72 ms 4164 KB Output is correct
3 Correct 62 ms 3932 KB Output is correct
4 Correct 164 ms 5456 KB Output is correct
5 Correct 96 ms 3964 KB Output is correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 4948 KB Output is correct
2 Correct 93 ms 4824 KB Output is correct
3 Correct 79 ms 4436 KB Output is correct
4 Correct 154 ms 5464 KB Output is correct
5 Correct 125 ms 4692 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 20308 KB Output is correct
2 Incorrect 508 ms 23744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 24140 KB Output is correct
2 Correct 480 ms 22688 KB Output is correct
3 Correct 396 ms 21704 KB Output is correct
4 Correct 770 ms 25172 KB Output is correct
5 Correct 681 ms 23236 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 24240 KB Output is correct
2 Incorrect 541 ms 28244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 523 ms 29008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 28244 KB Output is correct
2 Incorrect 620 ms 33112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 33876 KB Output is correct
2 Correct 634 ms 31568 KB Output is correct
3 Correct 538 ms 30548 KB Output is correct
4 Execution timed out 1077 ms 35668 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 32376 KB Output is correct
2 Incorrect 777 ms 37716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 38524 KB Output is correct
2 Correct 691 ms 35920 KB Output is correct
3 Correct 668 ms 34900 KB Output is correct
4 Execution timed out 1025 ms 40784 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 40276 KB Output is correct
2 Incorrect 945 ms 47188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 48208 KB Output is correct
2 Correct 897 ms 44780 KB Output is correct
3 Correct 835 ms 43856 KB Output is correct
4 Execution timed out 1077 ms 51284 KB Time limit exceeded
5 Halted 0 ms 0 KB -