Submission #314060

# Submission time Handle Problem Language Result Execution time Memory
314060 2020-10-18T03:38:33 Z shrek12357 Mobile (BOI12_mobile) C++14
90 / 100
1000 ms 35524 KB
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define ll long long
//cin.tie(0); ios_base::sync_with_stdio(0); 

double n, l;
vector<pair<double, double>> points;

bool check(double mid) {
	double left = 0;
	for (int i = 0; i < points.size(); i++) {
		if (left >= l) {
			return true;
		}
		if (mid < points[i].second) {
			continue;
		}
		double temp = sqrt(mid*mid - points[i].second*points[i].second);
		if (points[i].first - temp <= left) {
			left = max(points[i].first + temp, left);
		}
	}
	return left >= l;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0); 
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		double a, b;
		cin >> a >> b;
		points.push_back({ a, b });
	}
	double lo = 0;
	double hi = 1e10;
	double ans = 1e10;
	while (hi - lo > 1e-3) {
		double mid = (lo + hi) / 2;
		if (check(mid)) {
			ans = min(ans, mid);
			hi = mid;
		}
		else {
			lo = mid;
		}
	}
	printf("%.7lf\n", ans);
}

Compilation message

mobile.cpp: In function 'bool check(double)':
mobile.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 53 ms 2540 KB Output is correct
2 Correct 54 ms 2544 KB Output is correct
3 Correct 33 ms 1532 KB Output is correct
4 Correct 73 ms 2544 KB Output is correct
5 Correct 30 ms 1532 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 52 ms 2544 KB Output is correct
2 Correct 57 ms 2544 KB Output is correct
3 Correct 71 ms 2544 KB Output is correct
4 Correct 78 ms 2672 KB Output is correct
5 Correct 91 ms 2540 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 57 ms 2544 KB Output is correct
2 Correct 57 ms 2672 KB Output is correct
3 Correct 54 ms 2552 KB Output is correct
4 Correct 108 ms 2672 KB Output is correct
5 Correct 68 ms 2544 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 71 ms 2544 KB Output is correct
2 Correct 68 ms 2544 KB Output is correct
3 Correct 64 ms 2544 KB Output is correct
4 Correct 109 ms 2544 KB Output is correct
5 Correct 90 ms 2536 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 82 ms 2544 KB Output is correct
2 Correct 68 ms 2544 KB Output is correct
3 Correct 60 ms 2544 KB Output is correct
4 Correct 110 ms 2544 KB Output is correct
5 Correct 87 ms 2544 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 359 ms 8700 KB Output is correct
2 Correct 363 ms 8680 KB Output is correct
3 Correct 350 ms 15700 KB Output is correct
4 Correct 535 ms 17876 KB Output is correct
5 Correct 466 ms 15184 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 370 ms 8704 KB Output is correct
2 Correct 401 ms 15208 KB Output is correct
3 Correct 319 ms 14100 KB Output is correct
4 Correct 558 ms 17748 KB Output is correct
5 Correct 507 ms 15700 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 438 ms 16852 KB Output is correct
2 Correct 449 ms 25172 KB Output is correct
3 Correct 419 ms 24664 KB Output is correct
4 Correct 690 ms 27624 KB Output is correct
5 Correct 535 ms 24128 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 461 ms 16932 KB Output is correct
2 Correct 475 ms 23892 KB Output is correct
3 Correct 377 ms 23252 KB Output is correct
4 Correct 668 ms 27620 KB Output is correct
5 Correct 559 ms 24788 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 496 ms 17012 KB Output is correct
2 Correct 507 ms 25204 KB Output is correct
3 Correct 477 ms 24856 KB Output is correct
4 Correct 772 ms 27376 KB Output is correct
5 Correct 617 ms 23908 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 529 ms 16868 KB Output is correct
2 Correct 561 ms 23892 KB Output is correct
3 Correct 465 ms 23476 KB Output is correct
4 Correct 757 ms 27144 KB Output is correct
5 Correct 648 ms 24748 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 605 ms 16848 KB Output is correct
2 Correct 591 ms 25560 KB Output is correct
3 Correct 543 ms 24768 KB Output is correct
4 Correct 885 ms 28608 KB Output is correct
5 Correct 718 ms 24592 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 587 ms 17000 KB Output is correct
2 Correct 623 ms 24056 KB Output is correct
3 Correct 517 ms 23252 KB Output is correct
4 Correct 894 ms 28484 KB Output is correct
5 Correct 741 ms 24784 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 703 ms 16976 KB Output is correct
2 Correct 711 ms 31696 KB Output is correct
3 Correct 715 ms 30824 KB Output is correct
4 Execution timed out 1072 ms 35392 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 747 ms 20372 KB Output is correct
2 Correct 751 ms 29292 KB Output is correct
3 Correct 669 ms 28480 KB Output is correct
4 Execution timed out 1080 ms 35524 KB Time limit exceeded
5 Halted 0 ms 0 KB -