oj.uz

Submission #466651

# Submission time Handle Problem Language Result Execution time Memory
466651 2021-08-19T23:35:41 Z bill_lin Mobile (BOI12_mobile) C++14
100 / 100
 618 ms 22428 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
 
#define MOD 1000000007
#define INF 10000000

int n, l;

vector<pii> coords;

bool possible(ld curr) {
    ld right_bound = 0;
    for (int i = 0; i < n; i++) {
        if ((ld) coords[i].second * coords[i].second > curr * curr) continue;
        ld left_most = coords[i].first - sqrt(curr * curr - (ld) coords[i].second * coords[i].second);
        if (left_most <= right_bound) right_bound = max(right_bound, coords[i].first + sqrt(curr * curr - (ld) coords[i].second * coords[i].second));
        
    }
    return right_bound <= l;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
//    freopen("multimoo.in", "r", stdin);
//    freopen("multimoo.out", "w", stdout);
    
    cin >> n >> l;
    
    coords.resize(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        coords[i] = {x, y};
    }
    
    ld l = 0, r = 1000000000;
    for (int iteration = 0; iteration <= 50; iteration++) {
        ld mp = (l + r) / 2;
        if (possible(mp)) {
            l = mp;
        } else r = mp;
    }
    
    cout.precision(6);
    cout << fixed << l << '\n';
    
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 4 ms 420 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 324 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 916 KB Output is correct
2 Correct 46 ms 1100 KB Output is correct
3 Correct 29 ms 972 KB Output is correct
4 Correct 32 ms 1100 KB Output is correct
5 Correct 22 ms 972 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 972 KB Output is correct
2 Correct 31 ms 1100 KB Output is correct
3 Correct 34 ms 1092 KB Output is correct
4 Correct 33 ms 1100 KB Output is correct
5 Correct 35 ms 1228 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1028 KB Output is correct
2 Correct 50 ms 972 KB Output is correct
3 Correct 45 ms 1228 KB Output is correct
4 Correct 40 ms 1356 KB Output is correct
5 Correct 38 ms 1228 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1228 KB Output is correct
2 Correct 61 ms 1356 KB Output is correct
3 Correct 61 ms 1356 KB Output is correct
4 Correct 43 ms 1356 KB Output is correct
5 Correct 42 ms 1356 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1228 KB Output is correct
2 Correct 60 ms 1128 KB Output is correct
3 Correct 57 ms 1356 KB Output is correct
4 Correct 40 ms 1356 KB Output is correct
5 Correct 42 ms 1356 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 4240 KB Output is correct
2 Correct 300 ms 4420 KB Output is correct
3 Correct 310 ms 4356 KB Output is correct
4 Correct 192 ms 4356 KB Output is correct
5 Correct 219 ms 4428 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 4292 KB Output is correct
2 Correct 338 ms 4352 KB Output is correct
3 Correct 261 ms 4428 KB Output is correct
4 Correct 191 ms 4520 KB Output is correct
5 Correct 199 ms 4512 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 5000 KB Output is correct
2 Correct 367 ms 5188 KB Output is correct
3 Correct 367 ms 5252 KB Output is correct
4 Correct 233 ms 5316 KB Output is correct
5 Correct 249 ms 5460 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 5068 KB Output is correct
2 Correct 398 ms 5168 KB Output is correct
3 Correct 324 ms 5188 KB Output is correct
4 Correct 230 ms 5380 KB Output is correct
5 Correct 253 ms 5444 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 5788 KB Output is correct
2 Correct 425 ms 5956 KB Output is correct
3 Correct 422 ms 6084 KB Output is correct
4 Correct 276 ms 6060 KB Output is correct
5 Correct 310 ms 6116 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 5836 KB Output is correct
2 Correct 447 ms 5956 KB Output is correct
3 Correct 381 ms 6084 KB Output is correct
4 Correct 286 ms 6044 KB Output is correct
5 Correct 300 ms 6140 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 6604 KB Output is correct
2 Correct 475 ms 6476 KB Output is correct
3 Correct 500 ms 6704 KB Output is correct
4 Correct 316 ms 6704 KB Output is correct
5 Correct 326 ms 6664 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 6476 KB Output is correct
2 Correct 529 ms 6476 KB Output is correct
3 Correct 461 ms 6596 KB Output is correct
4 Correct 306 ms 6604 KB Output is correct
5 Correct 327 ms 6604 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 8140 KB Output is correct
2 Correct 617 ms 8520 KB Output is correct
3 Correct 603 ms 15952 KB Output is correct
4 Correct 408 ms 22428 KB Output is correct
5 Correct 423 ms 15708 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 8140 KB Output is correct
2 Correct 618 ms 8140 KB Output is correct
3 Correct 541 ms 15812 KB Output is correct
4 Correct 395 ms 8288 KB Output is correct
5 Correct 407 ms 15812 KB Output is correct