oj.uz

Submission #696443

# Submission time Handle Problem Language Result Execution time Memory
696443 2023-02-06T14:11:33 Z speedyArda Mobile (BOI12_mobile) C++14
100 / 100
 806 ms 74408 KB 
#include "bits/stdc++.h"

using namespace std;

const long long precision = 1e4; // TO not to deal with double/float precision problems // UPD: Didn't use it instaed used double 
const int MAXN = 1e6+5;

//long long stations[MAXN][2];
vector < vector<double> > stations;
int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	double  n, length;
	cin >> n >> length;
	//length *= precision;

	for(int i = 1; i <= n; i++)
	{
		double x, y;
		cin >> x >> y;
		//x *= precision;
		//y *= precision;
		if(stations.size() == 0 || (stations.back())[0] != x)
			stations.push_back({x, y});
		else 
		{
			vector<double> elem = stations.back();
			if(abs(elem[1]) > abs(y))
			{
				stations.pop_back();
				stations.push_back({x, y});
			}
		}
		/*cin >> stations[i][0] >> stations[i][1];
		stations[i][0]	*= precision;
		stations[i][1] *= precision;*/
	}



	double l = 0, r = 2.3e9, ans = 2.3e9; // Max distance will be 3e9 as we can we have 2e9 vertical and 2e9 horizontal distance so according to the pythagoran sqrt(2e9^2 + 2e9^2)  =  2e9 * sqrt(2)

	while(r - l >= 0.0001)
	{
		double m = (l + r) / 2.0000;
		double left = length, right = 0;
		for(int i = 0; i < stations.size(); i++)
		{	
			double x = stations[i][0], y = stations[i][1];
			//cout << x << " " << y << "\n";
			if(abs(y) > m)
				continue;
			
			double horizontal = sqrt((m * m) - (y * y));
			//cout << x << " " << y << " " << m << " " << horizontal << "\n";
			if(x <= 0)
			{	
				

				if(x + horizontal >= 0)
				{
					left = 0, right = max(right, (double) (x + horizontal)); 
				}

			} else 
			{
				double templeft = max((double)0.0000, (double)(x - horizontal));
				double tempright = min(length, (double)(x + horizontal));
				if(templeft <= right)
				{
					left = min(left, max((double)0.0000, templeft));
					right = max(right, min(length, tempright));
				}
			}
		}

		if(left <= 0 && right >= length)
		{
			ans = m;
			r = m - 0.0001;
		} else
			l = m + 0.0001;
	}


	cout << fixed << setprecision(10) << ans << "\n";



}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i = 0; i < stations.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 1 ms 212 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 508 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5688 KB Output is correct
2 Correct 48 ms 3748 KB Output is correct
3 Correct 33 ms 3388 KB Output is correct
4 Correct 56 ms 5680 KB Output is correct
5 Correct 25 ms 612 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 808 KB Output is correct
2 Correct 38 ms 3260 KB Output is correct
3 Correct 48 ms 5832 KB Output is correct
4 Correct 54 ms 5804 KB Output is correct
5 Correct 57 ms 5752 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5632 KB Output is correct
2 Correct 54 ms 3524 KB Output is correct
3 Correct 59 ms 5752 KB Output is correct
4 Correct 70 ms 6108 KB Output is correct
5 Correct 44 ms 1944 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3104 KB Output is correct
2 Correct 61 ms 3108 KB Output is correct
3 Correct 52 ms 1396 KB Output is correct
4 Correct 76 ms 6232 KB Output is correct
5 Correct 64 ms 5756 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5928 KB Output is correct
2 Correct 59 ms 3076 KB Output is correct
3 Correct 47 ms 1300 KB Output is correct
4 Correct 73 ms 5980 KB Output is correct
5 Correct 59 ms 5696 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 27868 KB Output is correct
2 Correct 270 ms 1168 KB Output is correct
3 Correct 240 ms 1208 KB Output is correct
4 Correct 376 ms 27900 KB Output is correct
5 Correct 304 ms 21072 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 1128 KB Output is correct
2 Correct 395 ms 27576 KB Output is correct
3 Correct 226 ms 5780 KB Output is correct
4 Correct 365 ms 27916 KB Output is correct
5 Correct 333 ms 25436 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 41556 KB Output is correct
2 Correct 291 ms 924 KB Output is correct
3 Correct 291 ms 908 KB Output is correct
4 Correct 454 ms 41560 KB Output is correct
5 Correct 354 ms 21016 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 1080 KB Output is correct
2 Correct 481 ms 41544 KB Output is correct
3 Correct 256 ms 5624 KB Output is correct
4 Correct 444 ms 41544 KB Output is correct
5 Correct 384 ms 41564 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 41512 KB Output is correct
2 Correct 345 ms 872 KB Output is correct
3 Correct 334 ms 1008 KB Output is correct
4 Correct 516 ms 41564 KB Output is correct
5 Correct 385 ms 21232 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 844 KB Output is correct
2 Correct 523 ms 41516 KB Output is correct
3 Correct 315 ms 7460 KB Output is correct
4 Correct 510 ms 41636 KB Output is correct
5 Correct 457 ms 41572 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 44404 KB Output is correct
2 Correct 392 ms 1936 KB Output is correct
3 Correct 387 ms 1892 KB Output is correct
4 Correct 587 ms 45504 KB Output is correct
5 Correct 510 ms 28968 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 1104 KB Output is correct
2 Correct 651 ms 43764 KB Output is correct
3 Correct 364 ms 7296 KB Output is correct
4 Correct 591 ms 44276 KB Output is correct
5 Correct 518 ms 41588 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 55608 KB Output is correct
2 Correct 491 ms 16176 KB Output is correct
3 Correct 498 ms 15120 KB Output is correct
4 Correct 749 ms 74176 KB Output is correct
5 Correct 569 ms 37232 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 664 KB Output is correct
2 Correct 734 ms 54320 KB Output is correct
3 Correct 479 ms 21048 KB Output is correct
4 Correct 806 ms 74408 KB Output is correct
5 Correct 647 ms 61028 KB Output is correct