Submission #658004

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658004	2022-11-11T19:53:45 Z	chjiao	Mobile (BOI12_mobile)	C++14	100 / 100	478 ms	31444 KB

mobile

//Binary search the shortest length from the firehose
 
#include <bits/stdc++.h>
using namespace std;
 
#define fastio	ios_base::sync_with_stdio(false);cin.tie(0)
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
 
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORB(i,a,b) for(ll i=a;i>=b;i--)
 
#define getbit(mask,i) ((mask>>(i))&1)
#define getnum(i) (1<<(i))
 
#define endl "\n"
#define sz(x) (int)size(x)
#define mp make_pair
using ll = long long;
const ll MOD1 = 1e9+7;
const ll MOD2 = 998244353;
const ll MN = 1e5;
const ll MAX = LLONG_MAX;
long double FLOAT_ERR = 1e-5;
long double first_true_float(long double lo, long double hi, function<bool(long double)> f) {
	// if none of the values in the range work, return hi + 1
	lo--;
	hi++;
	while (hi-lo > FLOAT_ERR) {
		long double mid =  (lo + hi) / 2.0f;
		if (f(mid)) {
			hi = mid;
		} else {
			lo = mid;
		}
	}
	return lo;
}
 
int main() {
    fastio;
	// freopen("XXX.in","r",stdin);
	// freopen("XXX.out","w",stdout);
    ll N;
    ll L;
    cin >> N >> L;
    vector<pair<ll,ll>> input(N);
    for(int i=0; i<N; i++){
        cin >> input[i].first >> input[i].second;
    }
    // sort(input.begin(), input.end());
    cout << fixed << setprecision(6)<<first_true_float(1, 1.5e9, [&](long double x){
        long double left = 0;
        for(auto cell:input){
            if(x*x < cell.second*cell.second){
                continue;
            }
            long double diviation = sqrt(x*x - cell.second*cell.second);
        
            if((cell.first-diviation) <= left){
                left =max(left, cell.first+diviation);
            } 
        }
        return left >= L;

    }) << endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	1620 KB	Output is correct
2	Correct	31 ms	1612 KB	Output is correct
3	Correct	18 ms	1672 KB	Output is correct
4	Correct	24 ms	2632 KB	Output is correct
5	Correct	14 ms	1480 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1620 KB	Output is correct
2	Correct	23 ms	1480 KB	Output is correct
3	Correct	27 ms	1712 KB	Output is correct
4	Correct	30 ms	1620 KB	Output is correct
5	Correct	26 ms	3072 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	1748 KB	Output is correct
2	Correct	30 ms	1748 KB	Output is correct
3	Correct	29 ms	2508 KB	Output is correct
4	Correct	30 ms	3780 KB	Output is correct
5	Correct	27 ms	2516 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	2004 KB	Output is correct
2	Correct	39 ms	3272 KB	Output is correct
3	Correct	34 ms	2904 KB	Output is correct
4	Correct	34 ms	3800 KB	Output is correct
5	Correct	29 ms	3028 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	2008 KB	Output is correct
2	Correct	41 ms	3276 KB	Output is correct
3	Correct	35 ms	2972 KB	Output is correct
4	Correct	29 ms	3776 KB	Output is correct
5	Correct	30 ms	3028 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	8276 KB	Output is correct
2	Correct	228 ms	15808 KB	Output is correct
3	Correct	188 ms	15288 KB	Output is correct
4	Correct	158 ms	17608 KB	Output is correct
5	Correct	155 ms	14908 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	182 ms	8276 KB	Output is correct
2	Correct	265 ms	14656 KB	Output is correct
3	Correct	156 ms	13764 KB	Output is correct
4	Correct	152 ms	17344 KB	Output is correct
5	Correct	155 ms	15428 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	9812 KB	Output is correct
2	Correct	237 ms	18924 KB	Output is correct
3	Correct	232 ms	18268 KB	Output is correct
4	Correct	180 ms	21464 KB	Output is correct
5	Correct	181 ms	17628 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	224 ms	9792 KB	Output is correct
2	Correct	318 ms	17496 KB	Output is correct
3	Correct	199 ms	16472 KB	Output is correct
4	Correct	184 ms	21332 KB	Output is correct
5	Correct	174 ms	18392 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	11396 KB	Output is correct
2	Correct	267 ms	22004 KB	Output is correct
3	Correct	273 ms	21384 KB	Output is correct
4	Correct	216 ms	24692 KB	Output is correct
5	Correct	213 ms	20212 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	273 ms	11316 KB	Output is correct
2	Correct	360 ms	20472 KB	Output is correct
3	Correct	229 ms	19532 KB	Output is correct
4	Correct	213 ms	24568 KB	Output is correct
5	Correct	213 ms	21368 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	306 ms	13008 KB	Output is correct
2	Correct	318 ms	25112 KB	Output is correct
3	Correct	299 ms	24352 KB	Output is correct
4	Correct	238 ms	28440 KB	Output is correct
5	Correct	267 ms	23968 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	13140 KB	Output is correct
2	Correct	393 ms	23316 KB	Output is correct
3	Correct	280 ms	22300 KB	Output is correct
4	Correct	252 ms	28188 KB	Output is correct
5	Correct	232 ms	24344 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	381 ms	16452 KB	Output is correct
2	Correct	426 ms	31444 KB	Output is correct
3	Correct	379 ms	30480 KB	Output is correct
4	Correct	299 ms	17148 KB	Output is correct
5	Correct	310 ms	29516 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	15980 KB	Output is correct
2	Correct	478 ms	29144 KB	Output is correct
3	Correct	339 ms	28364 KB	Output is correct
4	Correct	307 ms	17228 KB	Output is correct
5	Correct	291 ms	30684 KB	Output is correct

Submission #658004

Compilation message