oj.uz

Submission #1093747

# Submission time Handle Problem Language Result Execution time Memory
1093747 2024-09-27T11:04:06 Z michified Mobile (BOI12_mobile) C++17
50 / 100
 1000 ms 51280 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;
    }
    cout << setprecision(10) << l;
    return 0;
}

Subtask #1
4.0 / 4.0

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

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 612 KB Output is correct
2 Correct 4 ms 608 KB Output is correct
3 Correct 6 ms 608 KB Output is correct
4 Correct 7 ms 608 KB Output is correct
5 Correct 4 ms 652 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3424 KB Output is correct
2 Correct 78 ms 3912 KB Output is correct
3 Correct 38 ms 2652 KB Output is correct
4 Correct 95 ms 3924 KB Output is correct
5 Correct 41 ms 2396 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3420 KB Output is correct
2 Correct 78 ms 3420 KB Output is correct
3 Correct 91 ms 3864 KB Output is correct
4 Correct 97 ms 4044 KB Output is correct
5 Correct 148 ms 4420 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3676 KB Output is correct
2 Correct 65 ms 4144 KB Output is correct
3 Correct 60 ms 3920 KB Output is correct
4 Correct 152 ms 5456 KB Output is correct
5 Correct 88 ms 3928 KB Output is correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 4948 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 87 ms 4944 KB Output is correct
2 Correct 92 ms 4952 KB Output is correct
3 Correct 68 ms 4444 KB Output is correct
4 Correct 146 ms 5456 KB Output is correct
5 Correct 113 ms 4700 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 20172 KB Output is correct
2 Incorrect 403 ms 23636 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 414 ms 24136 KB Output is correct
2 Correct 424 ms 22688 KB Output is correct
3 Correct 352 ms 21828 KB Output is correct
4 Correct 737 ms 25164 KB Output is correct
5 Correct 608 ms 23240 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 24196 KB Output is correct
2 Incorrect 498 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 517 ms 28924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 28232 KB Output is correct
2 Incorrect 601 ms 33108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 33856 KB Output is correct
2 Correct 589 ms 31424 KB Output is correct
3 Correct 513 ms 30548 KB Output is correct
4 Execution timed out 1014 ms 35920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 32400 KB Output is correct
2 Incorrect 697 ms 37712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 38660 KB Output is correct
2 Correct 707 ms 35924 KB Output is correct
3 Correct 585 ms 34904 KB Output is correct
4 Execution timed out 1045 ms 40700 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 48244 KB Output is correct
2 Correct 833 ms 44908 KB Output is correct
3 Correct 717 ms 44020 KB Output is correct
4 Execution timed out 1041 ms 51280 KB Time limit exceeded
5 Halted 0 ms 0 KB -