oj.uz

Submission #398270

# Submission time Handle Problem Language Result Execution time Memory
398270 2021-05-04T04:31:41 Z AriaH Mobile (BOI12_mobile) C++11
50 / 100
 1000 ms 48064 KB 
/** vaziat sorati ghermeze **/

#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const ld one = 1.;
const ld eps = 1e-15;

int n, L, X[N], Y[N];

ld base[N];

pair < ld, ld > arr[N];

int check(ld x)
{
	int ptr = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(abs(Y[i]) - x > eps) continue;
		ld l = sqrt(x * x - base[i]);
		arr[ptr ++] = Mp(X[i] - l, X[i] + l);
	}
	sort(arr, arr + ptr);
	ld right = 0;
	for(int i = 0; i < ptr; i ++)
	{
		if(arr[i].F - right > eps)
		{
			return 0;
		}
		if(arr[i].S - right > eps)
		{
			right = arr[i].S;
		}
		if(right - L > eps)
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	scanf("%d%d", &n, &L);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d%d", &X[i], &Y[i]);
		base[i] = one * Y[i] * Y[i];
	}
	ld d = 0, up = 3e9;
	///printf("checking %d\n", check(6));
	for(int _ = 0; _ < 44; _ ++)
	{
		ld mid = (up + d) / 2.0;
		if(check(mid))
		{
			up = mid;
		}
		else
		{
			d = mid;
		}
	}
	printf("%.4lf", up);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d%d", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~
mobile.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%d%d", &X[i], &Y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.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 3 ms 320 KB Output is correct
4 Correct 4 ms 332 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 8 ms 560 KB Output is correct
3 Correct 12 ms 588 KB Output is correct
4 Correct 6 ms 460 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 536 KB Output is correct
2 Correct 8 ms 460 KB Output is correct
3 Correct 12 ms 528 KB Output is correct
4 Correct 7 ms 460 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 8 ms 460 KB Output is correct
3 Correct 13 ms 536 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 8 ms 460 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3420 KB Output is correct
2 Correct 256 ms 3788 KB Output is correct
3 Correct 131 ms 2608 KB Output is correct
4 Correct 113 ms 4004 KB Output is correct
5 Correct 92 ms 2252 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3504 KB Output is correct
2 Correct 112 ms 3228 KB Output is correct
3 Correct 127 ms 3876 KB Output is correct
4 Correct 126 ms 3988 KB Output is correct
5 Correct 128 ms 4484 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3740 KB Output is correct
2 Correct 291 ms 4040 KB Output is correct
3 Correct 340 ms 3916 KB Output is correct
4 Correct 95 ms 5272 KB Output is correct
5 Correct 151 ms 4016 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 5000 KB Output is correct
2 Correct 391 ms 4796 KB Output is correct
3 Correct 361 ms 4472 KB Output is correct
4 Correct 102 ms 5404 KB Output is correct
5 Correct 161 ms 4700 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 4968 KB Output is correct
2 Correct 391 ms 4812 KB Output is correct
3 Correct 345 ms 4512 KB Output is correct
4 Correct 115 ms 5376 KB Output is correct
5 Correct 172 ms 4724 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 20316 KB Output is correct
2 Execution timed out 1084 ms 23716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 24052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 24228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 28868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 28296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 33732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 32268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 38472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 40288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 48064 KB Time limit exceeded
2 Halted 0 ms 0 KB -