Submission #638433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638433	2022-09-06T00:39:40 Z	LeticiaFCS	Mobile (BOI12_mobile)	C++17	100 / 100	822 ms	30736 KB

mobile

#include "bits/stdc++.h"
#define st first
#define nd second
using lint = int64_t;
constexpr int MOD = int(1e9) + 7;
constexpr int INF = 0x3f3f3f3f;
constexpr int NINF = 0xcfcfcfcf;
constexpr lint LINF = 0x3f3f3f3f3f3f3f3f;
const long double PI = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

using ld = double;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	lint length;
	cin>>n>>length;
	vector<lint> x(n), y(n);
	for(int i=0; i<n; i++)
		cin>>x[i]>>y[i];
	
	ld l = 0, r = length;
	int it = 41;
	while(it--){
		ld mid = (l+r)/2;
		ld lastX = 0;
		for(int i=0; i<n; i++){
			ld xaux = sqrtl(mid*mid - y[i]*y[i]);
			ld a = x[i] - xaux;
			ld b = x[i] + xaux;
			if(a <= lastX + 1e-9)
				lastX = max(lastX, b);
		}
				
		if(length <= lastX + 1e-9) r = mid;
		else l = mid;
	}
	cout<<fixed<<setprecision(5)<<r<<"\n";
	

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

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	212 KB	Output is correct
3	Correct	1 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	320 KB	Output is correct
4	Correct	0 ms	316 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	340 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	324 KB	Output is correct
2	Correct	2 ms	468 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	4 ms	488 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	55 ms	2160 KB	Output is correct
2	Correct	27 ms	2164 KB	Output is correct
3	Correct	24 ms	1748 KB	Output is correct
4	Correct	61 ms	2132 KB	Output is correct
5	Correct	37 ms	1492 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	2180 KB	Output is correct
2	Correct	56 ms	2064 KB	Output is correct
3	Correct	62 ms	2228 KB	Output is correct
4	Correct	73 ms	2208 KB	Output is correct
5	Correct	69 ms	2316 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2332 KB	Output is correct
2	Correct	28 ms	2140 KB	Output is correct
3	Correct	36 ms	2260 KB	Output is correct
4	Correct	81 ms	2444 KB	Output is correct
5	Correct	74 ms	2364 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	2772 KB	Output is correct
2	Correct	34 ms	2516 KB	Output is correct
3	Correct	44 ms	2516 KB	Output is correct
4	Correct	85 ms	2528 KB	Output is correct
5	Correct	79 ms	2636 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	2772 KB	Output is correct
2	Correct	41 ms	2424 KB	Output is correct
3	Correct	44 ms	2508 KB	Output is correct
4	Correct	83 ms	2516 KB	Output is correct
5	Correct	76 ms	2516 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	9044 KB	Output is correct
2	Correct	175 ms	8792 KB	Output is correct
3	Correct	166 ms	8712 KB	Output is correct
4	Correct	393 ms	8788 KB	Output is correct
5	Correct	377 ms	8652 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	9040 KB	Output is correct
2	Correct	361 ms	8836 KB	Output is correct
3	Correct	218 ms	8532 KB	Output is correct
4	Correct	401 ms	8532 KB	Output is correct
5	Correct	383 ms	8532 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	10700 KB	Output is correct
2	Correct	209 ms	10344 KB	Output is correct
3	Correct	200 ms	10344 KB	Output is correct
4	Correct	485 ms	10436 KB	Output is correct
5	Correct	454 ms	10092 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	10604 KB	Output is correct
2	Correct	425 ms	10316 KB	Output is correct
3	Correct	267 ms	10096 KB	Output is correct
4	Correct	470 ms	10068 KB	Output is correct
5	Correct	460 ms	10092 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	220 ms	12168 KB	Output is correct
2	Correct	238 ms	11792 KB	Output is correct
3	Correct	230 ms	11860 KB	Output is correct
4	Correct	557 ms	11788 KB	Output is correct
5	Correct	526 ms	11724 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	12172 KB	Output is correct
2	Correct	490 ms	11848 KB	Output is correct
3	Correct	301 ms	11664 KB	Output is correct
4	Correct	565 ms	11604 KB	Output is correct
5	Correct	565 ms	11660 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	233 ms	13644 KB	Output is correct
2	Correct	284 ms	13268 KB	Output is correct
3	Correct	269 ms	13348 KB	Output is correct
4	Correct	637 ms	13352 KB	Output is correct
5	Correct	602 ms	13260 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	276 ms	13652 KB	Output is correct
2	Correct	593 ms	13352 KB	Output is correct
3	Correct	346 ms	13140 KB	Output is correct
4	Correct	645 ms	13092 KB	Output is correct
5	Correct	614 ms	13132 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	316 ms	16480 KB	Output is correct
2	Correct	340 ms	16224 KB	Output is correct
3	Correct	333 ms	16224 KB	Output is correct
4	Correct	802 ms	15992 KB	Output is correct
5	Correct	786 ms	29660 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	340 ms	15956 KB	Output is correct
2	Correct	706 ms	15980 KB	Output is correct
3	Correct	456 ms	16112 KB	Output is correct
4	Correct	822 ms	16076 KB	Output is correct
5	Correct	785 ms	30736 KB	Output is correct

Submission #638433

Compilation message