Submission #445889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445889	2021-07-20T05:19:28 Z	wind_reaper	Mobile (BOI12_mobile)	C++17	100 / 100	837 ms	27480 KB

mobile

#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************



//***************** GLOBAL VARIABLES *****************



//***************** AUXILIARY STRUCTS *****************



//***************** MAIN BODY *****************

void solve(){
	int N, L;
	cin >> N >> L;

	vector<array<int, 2>> A(N);
	for(auto& [x, y] : A)
		cin >> x >> y;

	double lo = 0, hi = sqrt(3e18);

	for(int _ = 0; _ < 70; _++){
		double mid = (lo + hi) / 2, maxl = 0;
		for(auto& [x, y] : A){
			double dx = sqrt(mid * mid - y * 1LL * y);
			if(x - dx <= maxl) maxl = max(maxl, x + dx);
		}

		(maxl < L ? lo : hi) = mid;
	}

	cout << fixed << setprecision(9) << (lo + hi) / 2 << '\n';
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic
*/

Subtask #1
4.0 / 4.0

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

Subtask #2
4.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	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	844 KB	Output is correct
2	Correct	41 ms	844 KB	Output is correct
3	Correct	29 ms	1356 KB	Output is correct
4	Correct	52 ms	1996 KB	Output is correct
5	Correct	29 ms	1080 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	856 KB	Output is correct
2	Correct	53 ms	844 KB	Output is correct
3	Correct	52 ms	844 KB	Output is correct
4	Correct	55 ms	2080 KB	Output is correct
5	Correct	59 ms	2400 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	972 KB	Output is correct
2	Correct	43 ms	844 KB	Output is correct
3	Correct	44 ms	1868 KB	Output is correct
4	Correct	71 ms	2988 KB	Output is correct
5	Correct	55 ms	1904 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	1100 KB	Output is correct
2	Correct	53 ms	1100 KB	Output is correct
3	Correct	52 ms	2124 KB	Output is correct
4	Correct	70 ms	3016 KB	Output is correct
5	Correct	63 ms	2240 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	1100 KB	Output is correct
2	Correct	53 ms	1100 KB	Output is correct
3	Correct	56 ms	2120 KB	Output is correct
4	Correct	71 ms	3008 KB	Output is correct
5	Correct	63 ms	2380 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	246 ms	4172 KB	Output is correct
2	Correct	271 ms	4172 KB	Output is correct
3	Correct	262 ms	11388 KB	Output is correct
4	Correct	353 ms	13752 KB	Output is correct
5	Correct	319 ms	11120 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	268 ms	4172 KB	Output is correct
2	Correct	459 ms	10820 KB	Output is correct
3	Correct	264 ms	9852 KB	Output is correct
4	Correct	349 ms	13564 KB	Output is correct
5	Correct	324 ms	11460 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	4940 KB	Output is correct
2	Correct	323 ms	4940 KB	Output is correct
3	Correct	317 ms	13584 KB	Output is correct
4	Correct	434 ms	16836 KB	Output is correct
5	Correct	389 ms	12928 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	319 ms	4940 KB	Output is correct
2	Correct	535 ms	12836 KB	Output is correct
3	Correct	325 ms	11716 KB	Output is correct
4	Correct	426 ms	16648 KB	Output is correct
5	Correct	389 ms	13636 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	338 ms	5708 KB	Output is correct
2	Correct	367 ms	5708 KB	Output is correct
3	Correct	372 ms	15900 KB	Output is correct
4	Correct	485 ms	19224 KB	Output is correct
5	Correct	447 ms	14740 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	370 ms	5708 KB	Output is correct
2	Correct	615 ms	15016 KB	Output is correct
3	Correct	373 ms	14148 KB	Output is correct
4	Correct	483 ms	19096 KB	Output is correct
5	Correct	457 ms	15892 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	393 ms	6476 KB	Output is correct
2	Correct	424 ms	6476 KB	Output is correct
3	Correct	427 ms	18116 KB	Output is correct
4	Correct	552 ms	22212 KB	Output is correct
5	Correct	513 ms	17828 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	428 ms	6476 KB	Output is correct
2	Correct	696 ms	17084 KB	Output is correct
3	Correct	421 ms	16192 KB	Output is correct
4	Correct	552 ms	21944 KB	Output is correct
5	Correct	527 ms	18116 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	491 ms	8140 KB	Output is correct
2	Correct	516 ms	8140 KB	Output is correct
3	Correct	523 ms	22596 KB	Output is correct
4	Correct	725 ms	27332 KB	Output is correct
5	Correct	656 ms	21704 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	541 ms	8140 KB	Output is correct
2	Correct	837 ms	21316 KB	Output is correct
3	Correct	557 ms	20420 KB	Output is correct
4	Correct	697 ms	27480 KB	Output is correct
5	Correct	652 ms	22980 KB	Output is correct

Submission #445889

Compilation message