oj.uz

Submission #714006

# Submission time Handle Problem Language Result Execution time Memory
714006 2023-03-23T13:34:18 Z magikrap Mobile (BOI12_mobile) C++14
100 / 100
 896 ms 35264 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>

#define ll long long
#define DBL_MAX 1.79769e+308
#define DBL_MIN -1.79769e+308

using namespace std;

ll N, L;
pair<ll, ll> arr[1000000];

bool check (double val) {
    // cout << endl;
    // cout << "val: " << val << endl;
    double right = 0;
    for (int i = 0; i < N; i++) {
        double x = (double) arr[i].first;
        double y = (double) arr[i].second;
        if (abs(y) > val) {
            continue;
        }
        double dist = sqrt(val*val - y*y);
        double l = x - dist;
        double r = x + dist;
        if (l < right) {
            right = max(right, r);
        }
    }
    //cout << "right: " << right << endl;
    if (right < L) {
        return true;
    } else {
        return false;
    }
}

int main() {
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        ll x, y;
        cin >> x >> y;
        arr[i] = {x, y};
    }
    sort(arr, arr + N, [](pair<ll, ll> a, pair<ll, ll> b) {
        if (a.first == b.first) {
            return abs(a.second) < abs(b.second);
        } else {
            return a.first < b.first;
        }
    });
    // cout << "arr: " << endl;
    // for (int i = 0; i < N; i++) {
    //     cout << fixed << setprecision(3) << arr[i].first << " " << arr[i].second << endl;
    // }
    double ans = 0;
    for (double diff = 1e9; diff > 0.00005; diff /= 2) {
        if (check(ans + diff)) {
            ans += diff;
        }
    }
    cout << fixed << setprecision(5) << ans << endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 452 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 448 KB Output is correct
5 Correct 4 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2072 KB Output is correct
2 Correct 58 ms 2544 KB Output is correct
3 Correct 40 ms 1656 KB Output is correct
4 Correct 64 ms 2576 KB Output is correct
5 Correct 28 ms 1356 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2124 KB Output is correct
2 Correct 47 ms 2172 KB Output is correct
3 Correct 62 ms 2548 KB Output is correct
4 Correct 59 ms 2680 KB Output is correct
5 Correct 69 ms 3020 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2276 KB Output is correct
2 Correct 71 ms 2696 KB Output is correct
3 Correct 57 ms 2624 KB Output is correct
4 Correct 104 ms 3724 KB Output is correct
5 Correct 56 ms 2560 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2496 KB Output is correct
2 Correct 75 ms 3184 KB Output is correct
3 Correct 67 ms 2876 KB Output is correct
4 Correct 82 ms 3784 KB Output is correct
5 Correct 74 ms 3104 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2468 KB Output is correct
2 Correct 94 ms 3148 KB Output is correct
3 Correct 61 ms 2764 KB Output is correct
4 Correct 85 ms 3752 KB Output is correct
5 Correct 69 ms 3020 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 8636 KB Output is correct
2 Correct 403 ms 10360 KB Output is correct
3 Correct 393 ms 10460 KB Output is correct
4 Correct 424 ms 10516 KB Output is correct
5 Correct 367 ms 14948 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 8812 KB Output is correct
2 Correct 408 ms 10392 KB Output is correct
3 Correct 334 ms 13852 KB Output is correct
4 Correct 416 ms 17436 KB Output is correct
5 Correct 372 ms 15508 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 10240 KB Output is correct
2 Correct 494 ms 11980 KB Output is correct
3 Correct 478 ms 11960 KB Output is correct
4 Correct 632 ms 12008 KB Output is correct
5 Correct 432 ms 17632 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 10328 KB Output is correct
2 Correct 512 ms 12124 KB Output is correct
3 Correct 398 ms 16580 KB Output is correct
4 Correct 515 ms 21516 KB Output is correct
5 Correct 441 ms 18480 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 11900 KB Output is correct
2 Correct 578 ms 13568 KB Output is correct
3 Correct 561 ms 13428 KB Output is correct
4 Correct 647 ms 13544 KB Output is correct
5 Correct 489 ms 20204 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 11808 KB Output is correct
2 Correct 568 ms 13604 KB Output is correct
3 Correct 528 ms 19752 KB Output is correct
4 Correct 588 ms 24504 KB Output is correct
5 Correct 520 ms 21364 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 13428 KB Output is correct
2 Correct 694 ms 15160 KB Output is correct
3 Correct 632 ms 24424 KB Output is correct
4 Correct 689 ms 28508 KB Output is correct
5 Correct 586 ms 23944 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 13524 KB Output is correct
2 Correct 666 ms 23384 KB Output is correct
3 Correct 568 ms 22444 KB Output is correct
4 Correct 722 ms 28260 KB Output is correct
5 Correct 628 ms 24428 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 16800 KB Output is correct
2 Correct 837 ms 18488 KB Output is correct
3 Correct 774 ms 30540 KB Output is correct
4 Correct 896 ms 35152 KB Output is correct
5 Correct 716 ms 29564 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 16904 KB Output is correct
2 Correct 797 ms 29164 KB Output is correct
3 Correct 677 ms 28360 KB Output is correct
4 Correct 860 ms 35264 KB Output is correct
5 Correct 733 ms 30672 KB Output is correct