Submission #88194

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88194	2018-12-04T10:25:21 Z	JustInCase	Mobile (BOI12_mobile)	C++17	70 / 100	803 ms	132096 KB

mobile

#include <bits/stdc++.h>

const int32_t MAX_N = 1e6;
const double EPS = 1e-6;

int32_t n, l;
std::pair< int32_t, int32_t > points[MAX_N + 5];

bool Check(double r) {
	std::vector< std::pair< double, bool > > events(2 * n);

	double curr = 0;
	for(int32_t i = 0; i < n; i++) {
		if(r * r < (int64_t) points[i].second * points[i].second) {
			continue;
		}

		double x1 = points[i].first - sqrt(r * r - (int64_t) points[i].second * points[i].second);
		double x2 = points[i].first + sqrt(r * r - (int64_t) points[i].second * points[i].second);

		if(!(x1 > curr)) {
			curr = std::max(curr, x2);
		}
	}

	if(!(curr < l)) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> l;

	for(int32_t i = 0; i < n; i++) {
		std::cin >> points[i].first >> points[i].second;
	}

	int64_t low = 1, high = 1e16;
	double ans;
	while(low <= high) {
		int64_t mid = (low + high) / 2;

		if(Check(mid / 10000.0)) {
			ans = mid / 10000.0;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}

	std::cout << std::fixed << std::setprecision(7);
	std::cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	560 KB	Output is correct
2	Correct	2 ms	564 KB	Output is correct
3	Correct	3 ms	568 KB	Output is correct
4	Correct	3 ms	700 KB	Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	980 KB	Output is correct
2	Correct	6 ms	1040 KB	Output is correct
3	Correct	5 ms	1108 KB	Output is correct
4	Correct	6 ms	1148 KB	Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1332 KB	Output is correct
2	Correct	6 ms	1460 KB	Output is correct
3	Correct	5 ms	1460 KB	Output is correct
4	Correct	5 ms	1460 KB	Output is correct
5	Correct	5 ms	1460 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	4192 KB	Output is correct
2	Correct	49 ms	4500 KB	Output is correct
3	Correct	33 ms	4500 KB	Output is correct
4	Correct	44 ms	4500 KB	Output is correct
5	Correct	28 ms	4500 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	4500 KB	Output is correct
2	Correct	41 ms	4500 KB	Output is correct
3	Correct	47 ms	4500 KB	Output is correct
4	Correct	46 ms	4500 KB	Output is correct
5	Correct	51 ms	4608 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	4736 KB	Output is correct
2	Correct	52 ms	4736 KB	Output is correct
3	Correct	49 ms	4736 KB	Output is correct
4	Correct	61 ms	5136 KB	Output is correct
5	Correct	52 ms	5136 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	5324 KB	Output is correct
2	Correct	66 ms	6596 KB	Output is correct
3	Correct	60 ms	7620 KB	Output is correct
4	Correct	63 ms	9600 KB	Output is correct
5	Correct	59 ms	10884 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	10884 KB	Output is correct
2	Correct	64 ms	10968 KB	Output is correct
3	Correct	60 ms	11536 KB	Output is correct
4	Correct	61 ms	11540 KB	Output is correct
5	Correct	57 ms	11624 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	371 ms	27740 KB	Output is correct
2	Correct	437 ms	28332 KB	Output is correct
3	Correct	403 ms	28332 KB	Output is correct
4	Correct	392 ms	28332 KB	Output is correct
5	Correct	407 ms	28332 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	410 ms	28332 KB	Output is correct
2	Correct	454 ms	28332 KB	Output is correct
3	Correct	378 ms	28332 KB	Output is correct
4	Correct	391 ms	28332 KB	Output is correct
5	Correct	396 ms	28332 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	32184 KB	Output is correct
2	Correct	526 ms	41640 KB	Output is correct
3	Correct	508 ms	50288 KB	Output is correct
4	Correct	470 ms	62148 KB	Output is correct
5	Correct	484 ms	70056 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	487 ms	70100 KB	Output is correct
2	Correct	516 ms	78100 KB	Output is correct
3	Correct	461 ms	84872 KB	Output is correct
4	Correct	432 ms	96684 KB	Output is correct
5	Correct	431 ms	105504 KB	Output is correct

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	556 ms	109412 KB	Output is correct
2	Correct	565 ms	120168 KB	Output is correct
3	Correct	558 ms	130360 KB	Output is correct
4	Runtime error	529 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	544 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	600 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	612 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	739 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	803 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

Submission #88194

Compilation message