Submission #660612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660612	2022-11-22T15:41:39 Z	SansPapyrus683	Mobile (BOI12_mobile)	C++17	100 / 100	944 ms	35392 KB

mobile

#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
using Point = std::pair<long long, long long>;

constexpr int PRECISION = 4;

double dist(const Point& p1, const Point& p2) {
    long long dx = p1.first - p2.first;
    long long dy = p1.second - p2.second;
    return std::sqrt(dx * dx + dy * dy);
}

/**
 * https://oj.uz/problem/view/BOI12_mobile
 * 2 10
 * 0 0
 * 11 1 should output something close to 5.545455
 */
int main() {
    int tower_num;
    int road_len;
    std::cin >> tower_num >> road_len;

    vector<Point> towers(tower_num);
    for (Point& t : towers) {
        std::cin >> t.first >> t.second;
    }
    std::sort(towers.begin(), towers.end());

    long long div_by = std::pow(10, PRECISION);
    long long lo = 0;
    long long hi = INT64_MAX / 2;
    long long valid = -1;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        double power = (double) mid / div_by;

        double at = 0;
        for (Point& t : towers) {
            double sqrt = std::sqrt(power * power - t.second * t.second);
            double start = -sqrt + t.first;
            double end = sqrt + t.first;
            if (start <= at) {
                at = std::max(at, end);
            }
        }

        if (at >= road_len) {
            valid = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    cout << std::fixed << std::setprecision(PRECISION)
         << (double) valid / div_by << endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	1464 KB	Output is correct
2	Correct	58 ms	1492 KB	Output is correct
3	Correct	38 ms	1256 KB	Output is correct
4	Correct	63 ms	1620 KB	Output is correct
5	Correct	33 ms	1108 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	1492 KB	Output is correct
2	Correct	52 ms	1400 KB	Output is correct
3	Correct	69 ms	1492 KB	Output is correct
4	Correct	66 ms	1620 KB	Output is correct
5	Correct	76 ms	1780 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	1668 KB	Output is correct
2	Correct	62 ms	1584 KB	Output is correct
3	Correct	71 ms	1744 KB	Output is correct
4	Correct	99 ms	1976 KB	Output is correct
5	Correct	63 ms	1812 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	1748 KB	Output is correct
2	Correct	80 ms	1984 KB	Output is correct
3	Correct	86 ms	2060 KB	Output is correct
4	Correct	94 ms	1980 KB	Output is correct
5	Correct	76 ms	1984 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	1852 KB	Output is correct
2	Correct	76 ms	1976 KB	Output is correct
3	Correct	76 ms	1984 KB	Output is correct
4	Correct	95 ms	1984 KB	Output is correct
5	Correct	78 ms	2004 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	8120 KB	Output is correct
2	Correct	387 ms	15848 KB	Output is correct
3	Correct	376 ms	15272 KB	Output is correct
4	Correct	472 ms	17612 KB	Output is correct
5	Correct	397 ms	14892 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	392 ms	8020 KB	Output is correct
2	Correct	433 ms	8244 KB	Output is correct
3	Correct	331 ms	8248 KB	Output is correct
4	Correct	466 ms	8244 KB	Output is correct
5	Correct	397 ms	8244 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	351 ms	9684 KB	Output is correct
2	Correct	470 ms	18884 KB	Output is correct
3	Correct	443 ms	18384 KB	Output is correct
4	Correct	569 ms	21580 KB	Output is correct
5	Correct	470 ms	17636 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	499 ms	9684 KB	Output is correct
2	Correct	533 ms	9812 KB	Output is correct
3	Correct	396 ms	9812 KB	Output is correct
4	Correct	578 ms	9808 KB	Output is correct
5	Correct	491 ms	9812 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	411 ms	11252 KB	Output is correct
2	Correct	552 ms	22000 KB	Output is correct
3	Correct	529 ms	21496 KB	Output is correct
4	Correct	668 ms	24800 KB	Output is correct
5	Correct	538 ms	20416 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	563 ms	11252 KB	Output is correct
2	Correct	597 ms	11380 KB	Output is correct
3	Correct	479 ms	11380 KB	Output is correct
4	Correct	654 ms	11376 KB	Output is correct
5	Correct	552 ms	11376 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	470 ms	12884 KB	Output is correct
2	Correct	640 ms	25240 KB	Output is correct
3	Correct	597 ms	24484 KB	Output is correct
4	Correct	763 ms	28448 KB	Output is correct
5	Correct	628 ms	24068 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	658 ms	13072 KB	Output is correct
2	Correct	688 ms	13064 KB	Output is correct
3	Correct	552 ms	13072 KB	Output is correct
4	Correct	933 ms	13068 KB	Output is correct
5	Correct	651 ms	13076 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	584 ms	16292 KB	Output is correct
2	Correct	787 ms	31660 KB	Output is correct
3	Correct	761 ms	30516 KB	Output is correct
4	Correct	944 ms	35392 KB	Output is correct
5	Correct	809 ms	29544 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	802 ms	15972 KB	Output is correct
2	Correct	845 ms	16332 KB	Output is correct
3	Correct	706 ms	16336 KB	Output is correct
4	Correct	932 ms	15956 KB	Output is correct
5	Correct	800 ms	16280 KB	Output is correct

Submission #660612

Compilation message