Submission #964131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964131	2024-04-16T10:52:12 Z	dubabuba	Mobile (BOI12_mobile)	C++14	100 / 100	778 ms	16144 KB

mobile

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("lzcnt", "popcnt")
 
typedef pair<int, int> pii;
#define x first
#define y second
#define MP make_pair
 
const int mxn = 1e6 + 10;
pii P[mxn];
int n, m;
 
bool can(double r) {
	double sus = 0;
	for(int i = 1; i <= n; i++) {
		double x = P[i].x;
		double y = abs(P[i].y);
		if(y > r) continue;
		double d = sqrt(r * r - y * y);
		double L = x - d, R = x + d;
		if(sus >= L) sus = max(sus, R);
	}
	return sus >= 1.0 * m;
}
 
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> P[i].x >> P[i].y;
 
	double L = 0, R = 1e18;
	while(R - L > 0.0000001) {
		double M = (L + R) / 2;
		if(can(M)) R = M;
		else L = M;
	}
	printf("%.6lf\n", L);
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	516 KB	Output is correct
2	Correct	4 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	4 ms	344 KB	Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	3160 KB	Output is correct
2	Correct	64 ms	3432 KB	Output is correct
3	Correct	33 ms	3164 KB	Output is correct
4	Correct	53 ms	3416 KB	Output is correct
5	Correct	27 ms	3040 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	3440 KB	Output is correct
2	Correct	42 ms	3420 KB	Output is correct
3	Correct	50 ms	3412 KB	Output is correct
4	Correct	52 ms	3228 KB	Output is correct
5	Correct	60 ms	3672 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	3296 KB	Output is correct
2	Correct	61 ms	3552 KB	Output is correct
3	Correct	52 ms	3348 KB	Output is correct
4	Correct	74 ms	3764 KB	Output is correct
5	Correct	51 ms	3380 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	3900 KB	Output is correct
2	Correct	69 ms	3804 KB	Output is correct
3	Correct	59 ms	3408 KB	Output is correct
4	Correct	74 ms	3932 KB	Output is correct
5	Correct	69 ms	3420 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	3820 KB	Output is correct
2	Correct	73 ms	3800 KB	Output is correct
3	Correct	61 ms	3420 KB	Output is correct
4	Correct	73 ms	3832 KB	Output is correct
5	Correct	61 ms	3424 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	300 ms	7500 KB	Output is correct
2	Correct	363 ms	8784 KB	Output is correct
3	Correct	369 ms	8520 KB	Output is correct
4	Correct	356 ms	9672 KB	Output is correct
5	Correct	328 ms	8264 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	376 ms	9328 KB	Output is correct
2	Correct	415 ms	8288 KB	Output is correct
3	Correct	319 ms	7756 KB	Output is correct
4	Correct	354 ms	9540 KB	Output is correct
5	Correct	330 ms	8648 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	354 ms	10360 KB	Output is correct
2	Correct	430 ms	11464 KB	Output is correct
3	Correct	428 ms	11220 KB	Output is correct
4	Correct	462 ms	13152 KB	Output is correct
5	Correct	396 ms	11100 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	448 ms	12380 KB	Output is correct
2	Correct	499 ms	10844 KB	Output is correct
3	Correct	370 ms	10336 KB	Output is correct
4	Correct	509 ms	13020 KB	Output is correct
5	Correct	429 ms	11356 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	426 ms	10320 KB	Output is correct
2	Correct	505 ms	12384 KB	Output is correct
3	Correct	484 ms	12368 KB	Output is correct
4	Correct	507 ms	13900 KB	Output is correct
5	Correct	448 ms	11612 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	569 ms	13148 KB	Output is correct
2	Correct	553 ms	11608 KB	Output is correct
3	Correct	433 ms	11104 KB	Output is correct
4	Correct	514 ms	13528 KB	Output is correct
5	Correct	457 ms	12380 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	495 ms	10768 KB	Output is correct
2	Correct	571 ms	13144 KB	Output is correct
3	Correct	578 ms	12772 KB	Output is correct
4	Correct	584 ms	14780 KB	Output is correct
5	Correct	506 ms	12636 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	613 ms	14048 KB	Output is correct
2	Correct	630 ms	12384 KB	Output is correct
3	Correct	497 ms	11868 KB	Output is correct
4	Correct	574 ms	14688 KB	Output is correct
5	Correct	516 ms	12896 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	613 ms	13084 KB	Output is correct
2	Correct	733 ms	16144 KB	Output is correct
3	Correct	716 ms	15664 KB	Output is correct
4	Correct	775 ms	8040 KB	Output is correct
5	Correct	611 ms	8024 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	751 ms	8028 KB	Output is correct
2	Correct	778 ms	8232 KB	Output is correct
3	Correct	657 ms	8028 KB	Output is correct
4	Correct	724 ms	8236 KB	Output is correct
5	Correct	634 ms	8468 KB	Output is correct

Submission #964131

Compilation message