Submission #321582

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321582	2020-11-12T19:39:22 Z	CSQ31	Mobile (BOI12_mobile)	C++14	50 / 100	1000 ms	65288 KB

mobile

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+9)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int main()
{
	owo
	int n;
	cin>>n;
	ld L;cin>>L;
	vector<ld>x(n),y(n);
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	ld l = 1,r = 1e9+2;
	while(r-l>1e-4){
		ld mid = (l+r)/2;
		vector<ld>lf(n),rg(n);
		for(int i=0;i<n;i++){
			if(y[i] > mid){
				lf[i] = 1e9+1;
				rg[i] = -1e9;
				continue;
			}
			ld dist = sqrt(mid*mid - y[i]*y[i]);
			lf[i] = x[i]-dist;
			rg[i] = x[i]+dist;
		}
		ld cur = 0;
		for(int i=0;i<n;i++){
			if(cur >=lf[i])cur=max(cur,rg[i]);
		}
		if(cur >= L)r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(4)<<l;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	708 KB	Output is correct
2	Correct	11 ms	708 KB	Output is correct
3	Correct	10 ms	712 KB	Output is correct
4	Correct	13 ms	708 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	708 KB	Output is correct
2	Correct	11 ms	708 KB	Output is correct
3	Correct	10 ms	708 KB	Output is correct
4	Correct	14 ms	832 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	708 KB	Output is correct
2	Correct	11 ms	708 KB	Output is correct
3	Correct	10 ms	708 KB	Output is correct
4	Correct	14 ms	708 KB	Output is correct
5	Correct	11 ms	700 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	5120 KB	Output is correct
2	Correct	195 ms	5216 KB	Output is correct
3	Correct	127 ms	3748 KB	Output is correct
4	Correct	221 ms	5148 KB	Output is correct
5	Correct	124 ms	3600 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	5312 KB	Output is correct
2	Correct	197 ms	4856 KB	Output is correct
3	Correct	234 ms	5552 KB	Output is correct
4	Correct	233 ms	5380 KB	Output is correct
5	Correct	266 ms	6060 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	5968 KB	Output is correct
2	Correct	212 ms	5572 KB	Output is correct
3	Correct	208 ms	5824 KB	Output is correct
4	Correct	319 ms	6700 KB	Output is correct
5	Correct	248 ms	5988 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	256 ms	6800 KB	Output is correct
2	Correct	259 ms	6684 KB	Output is correct
3	Correct	248 ms	6736 KB	Output is correct
4	Correct	313 ms	6796 KB	Output is correct
5	Correct	291 ms	6668 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	262 ms	6732 KB	Output is correct
2	Correct	255 ms	6680 KB	Output is correct
3	Correct	248 ms	6840 KB	Output is correct
4	Correct	322 ms	6764 KB	Output is correct
5	Correct	286 ms	6680 KB	Output is correct

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1056 ms	31864 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	1085 ms	38392 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	38136 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	1093 ms	44340 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	1089 ms	44384 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	1058 ms	50652 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	1060 ms	50508 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	1039 ms	63276 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	1090 ms	65288 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #321582

Compilation message