oj.uz

Submission #1093736

# Submission time Handle Problem Language Result Execution time Memory
1093736 2024-09-27T10:56:14 Z michified Mobile (BOI12_mobile) C++17
50 / 100
 1000 ms 46476 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 = sqrtl(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.0001;
    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 0 ms 344 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 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 552 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3420 KB Output is correct
2 Correct 62 ms 3548 KB Output is correct
3 Correct 70 ms 2624 KB Output is correct
4 Correct 98 ms 3412 KB Output is correct
5 Correct 45 ms 2140 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3392 KB Output is correct
2 Correct 82 ms 3420 KB Output is correct
3 Correct 100 ms 3744 KB Output is correct
4 Correct 112 ms 3668 KB Output is correct
5 Correct 124 ms 4132 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3688 KB Output is correct
2 Correct 68 ms 3664 KB Output is correct
3 Correct 80 ms 3644 KB Output is correct
4 Correct 164 ms 4824 KB Output is correct
5 Correct 106 ms 3752 KB Output is correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 4432 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 119 ms 4488 KB Output is correct
2 Correct 94 ms 4432 KB Output is correct
3 Correct 108 ms 4328 KB Output is correct
4 Correct 150 ms 4728 KB Output is correct
5 Correct 136 ms 4176 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 18316 KB Output is correct
2 Incorrect 440 ms 20008 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 425 ms 20252 KB Output is correct
2 Correct 431 ms 19480 KB Output is correct
3 Correct 357 ms 19024 KB Output is correct
4 Correct 690 ms 20820 KB Output is correct
5 Correct 590 ms 19792 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 22032 KB Output is correct
2 Incorrect 505 ms 23956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 25428 KB Output is correct
2 Incorrect 616 ms 28048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 29332 KB Output is correct
2 Correct 622 ms 29772 KB Output is correct
3 Correct 520 ms 29004 KB Output is correct
4 Execution timed out 1012 ms 32796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 35668 KB Output is correct
2 Correct 707 ms 33824 KB Output is correct
3 Correct 590 ms 33132 KB Output is correct
4 Execution timed out 1040 ms 37372 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 38484 KB Output is correct
2 Incorrect 883 ms 43756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 44540 KB Output is correct
2 Correct 851 ms 42064 KB Output is correct
3 Correct 748 ms 41160 KB Output is correct
4 Execution timed out 1020 ms 46476 KB Time limit exceeded
5 Halted 0 ms 0 KB -