Submission #445888

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445888	2021-07-20T05:18:24 Z	wind_reaper	Mobile (BOI12_mobile)	C++17	12 / 100	550 ms	23616 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 * 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	0 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	1 ms	204 KB	Output is correct
4	Correct	1 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	320 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct

Subtask #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	Incorrect	5 ms	332 KB	Output isn't correct

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	332 KB	Output is correct
2	Correct	4 ms	332 KB	Output is correct
3	Correct	4 ms	320 KB	Output is correct
4	Incorrect	5 ms	332 KB	Output isn't correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 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	Incorrect	5 ms	332 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	844 KB	Output is correct
2	Correct	48 ms	1612 KB	Output is correct
3	Incorrect	72 ms	1976 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	6552 KB	Output is correct
2	Incorrect	425 ms	18980 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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

Submission #445888

Compilation message