Submission #466647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
466647	2021-08-19T23:14:01 Z	bill_lin	Mobile (BOI12_mobile)	C++14	0 / 100	1000 ms	12096 KB

mobile

#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++) {
        ld left_most = coords[i].first - sqrt(curr * curr - (ld) coords[i].second * coords[i].second);
        if (left_most > right_bound) return true;
        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 = 1e9;
    for (int iteration = 0; iteration <= 50; iteration++) {
        ld mp = (l + r) / 2;
        if (possible(mp)) {
            l = mp;
        } else r = mp;
    }
    
    cout.precision(10);
    cout << fixed << l << '\n';
    
}

Subtask #1
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Incorrect	204 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
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	Incorrect	0 ms	204 KB	Output isn't correct

Subtask #3
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	332 KB	Output is correct
2	Correct	3 ms	332 KB	Output is correct
3	Incorrect	4 ms	332 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	356 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	120 ms	844 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	146 ms	844 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	972 KB	Output is correct
2	Incorrect	36 ms	844 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	36 ms	1100 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	1100 KB	Output is correct
2	Incorrect	51 ms	1100 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	4172 KB	Output is correct
2	Correct	209 ms	4172 KB	Output is correct
3	Correct	237 ms	11332 KB	Output is correct
4	Execution timed out	1068 ms	11288 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	168 ms	4172 KB	Output is correct
2	Incorrect	773 ms	4172 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	346 ms	4940 KB	Output is correct
2	Incorrect	252 ms	4940 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	231 ms	4940 KB	Output is correct
2	Incorrect	918 ms	12096 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	398 ms	5708 KB	Output is correct
2	Incorrect	295 ms	5708 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	275 ms	5708 KB	Output is correct
2	Execution timed out	1086 ms	5708 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	456 ms	6476 KB	Output is correct
2	Incorrect	330 ms	6476 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	311 ms	6476 KB	Output is correct
2	Execution timed out	1087 ms	6476 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	584 ms	8140 KB	Output is correct
2	Incorrect	467 ms	8140 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	328 ms	8140 KB	Output is correct
2	Execution timed out	1090 ms	8140 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Submission #466647

Compilation message