oj.uz

Submission #466650

# Submission time Handle Problem Language Result Execution time Memory
466650 2021-08-19T23:34:52 Z bill_lin Mobile (BOI12_mobile) C++14
90 / 100
 1000 ms 14216 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 <= 100; 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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 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 3 ms 332 KB Output is correct
2 Correct 3 ms 352 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 844 KB Output is correct
2 Correct 80 ms 1996 KB Output is correct
3 Correct 45 ms 1356 KB Output is correct
4 Correct 40 ms 2052 KB Output is correct
5 Correct 27 ms 1020 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 844 KB Output is correct
2 Correct 38 ms 1612 KB Output is correct
3 Correct 43 ms 1864 KB Output is correct
4 Correct 43 ms 2124 KB Output is correct
5 Correct 46 ms 2400 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 972 KB Output is correct
2 Correct 82 ms 956 KB Output is correct
3 Correct 69 ms 1868 KB Output is correct
4 Correct 50 ms 3012 KB Output is correct
5 Correct 47 ms 1868 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1152 KB Output is correct
2 Correct 100 ms 2508 KB Output is correct
3 Correct 84 ms 2124 KB Output is correct
4 Correct 51 ms 3012 KB Output is correct
5 Correct 53 ms 2252 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1100 KB Output is correct
2 Correct 100 ms 972 KB Output is correct
3 Correct 81 ms 2108 KB Output is correct
4 Correct 53 ms 3008 KB Output is correct
5 Correct 52 ms 2376 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 4172 KB Output is correct
2 Correct 501 ms 4172 KB Output is correct
3 Correct 503 ms 4172 KB Output is correct
4 Correct 240 ms 4172 KB Output is correct
5 Correct 257 ms 10988 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 4172 KB Output is correct
2 Correct 616 ms 4172 KB Output is correct
3 Correct 415 ms 9832 KB Output is correct
4 Correct 251 ms 11368 KB Output is correct
5 Correct 281 ms 11376 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 4940 KB Output is correct
2 Correct 621 ms 4996 KB Output is correct
3 Correct 604 ms 12100 KB Output is correct
4 Correct 300 ms 12116 KB Output is correct
5 Correct 316 ms 12068 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 4940 KB Output is correct
2 Correct 700 ms 4940 KB Output is correct
3 Correct 486 ms 11716 KB Output is correct
4 Correct 295 ms 12188 KB Output is correct
5 Correct 299 ms 12108 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 5708 KB Output is correct
2 Correct 654 ms 5708 KB Output is correct
3 Correct 705 ms 12948 KB Output is correct
4 Correct 344 ms 12976 KB Output is correct
5 Correct 363 ms 13228 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 5708 KB Output is correct
2 Correct 805 ms 5708 KB Output is correct
3 Correct 590 ms 12868 KB Output is correct
4 Correct 350 ms 12920 KB Output is correct
5 Correct 350 ms 13344 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 6476 KB Output is correct
2 Correct 795 ms 6724 KB Output is correct
3 Correct 828 ms 13764 KB Output is correct
4 Correct 392 ms 13768 KB Output is correct
5 Correct 412 ms 14148 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 6692 KB Output is correct
2 Correct 841 ms 6724 KB Output is correct
3 Correct 648 ms 14216 KB Output is correct
4 Correct 408 ms 14068 KB Output is correct
5 Correct 406 ms 14020 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 8268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 8268 KB Output is correct
2 Execution timed out 1020 ms 8260 KB Time limit exceeded
3 Halted 0 ms 0 KB -