답안 #91788 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91788	2018-12-30T02:56:40 Z	updown1	Mobile (BOI12_mobile)	C++17	95 / 100	1000 ms	33984 KB

mobile

/*
binary search on the answer
to test a value x, for all the circles come up with ranges of the line that is covered if the circle has a radius x
find the minimum value x s.t. the whole line is covered
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//#define double long double
const int MAXN=1000000, INF=1000000000000000000;
///500,000,000
int N, L;
pair<double, double> pts[MAXN], rng[MAXN];

bool full(double rr) {
    /// make the ranges
    ffi {
        int x = pts[i].a, y = pts[i].b;
        if (y*y > rr*rr) {rng[i] = mp(0, 0); continue;}
        double a = sqrt((long double)rr*rr-y*y);
        double l = x - a; double r = x + a;
        l = max(l, (double) 0); l = min(l, (double)L);
        r = max(r, (double) 0); r = min(r, (double)L);
        rng[i] = mp(l, r);
    }
    //w<< rr<<e; ffi w<< rng[i].a s rng[i].b<<e;
    /// see if the whole range is covered
    double far = 0;
    ffi {
        if (rng[i].a > far) continue;
        far = max(far, rng[i].b);
    }
    return far >=L;
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> L;
	double a = 2236067978, b = 2236067978;
	ffi {
	    cin >> pts[i].a >> pts[i].b;
	    double x = pts[i].a, y = pts[i].b;
	    double use1 = sqrt((long double)x*x+y*y);
	    double use2 = sqrt((long double)(x-L)*(x-L)+y*y);
	    b = min(b, max(use1, use2));
	    a = min(a, min(use1, use2));
	}
	while (b-a > .001) {
        double mid = (a+b)/2;
        if (full(mid)) b = mid;
        else a = mid;
	}
	w<< fixed << setprecision(6) <<a<<e;
}

Compilation message

mobile.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	4 ms	504 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	5 ms	504 KB	Output is correct
3	Correct	4 ms	504 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	6 ms	504 KB	Output is correct
3	Correct	4 ms	504 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	6 ms	508 KB	Output is correct
3	Correct	4 ms	504 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	4 ms	504 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	3448 KB	Output is correct
2	Correct	66 ms	3804 KB	Output is correct
3	Correct	38 ms	2680 KB	Output is correct
4	Correct	51 ms	3832 KB	Output is correct
5	Correct	25 ms	2296 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	3528 KB	Output is correct
2	Correct	42 ms	3320 KB	Output is correct
3	Correct	50 ms	3884 KB	Output is correct
4	Correct	55 ms	4020 KB	Output is correct
5	Correct	135 ms	4472 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	3748 KB	Output is correct
2	Correct	69 ms	4004 KB	Output is correct
3	Correct	56 ms	3960 KB	Output is correct
4	Correct	75 ms	5416 KB	Output is correct
5	Correct	50 ms	3960 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	4984 KB	Output is correct
2	Correct	83 ms	4788 KB	Output is correct
3	Correct	63 ms	4472 KB	Output is correct
4	Correct	77 ms	5332 KB	Output is correct
5	Correct	61 ms	4728 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	4984 KB	Output is correct
2	Correct	83 ms	4856 KB	Output is correct
3	Correct	64 ms	4404 KB	Output is correct
4	Correct	80 ms	5380 KB	Output is correct
5	Correct	63 ms	4748 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	414 ms	18936 KB	Output is correct
2	Correct	438 ms	23928 KB	Output is correct
3	Correct	412 ms	23304 KB	Output is correct
4	Correct	388 ms	25636 KB	Output is correct
5	Correct	314 ms	22904 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	477 ms	19648 KB	Output is correct
2	Correct	443 ms	17652 KB	Output is correct
3	Correct	335 ms	17792 KB	Output is correct
4	Correct	389 ms	17784 KB	Output is correct
5	Correct	332 ms	17708 KB	Output is correct

Subtask #14
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	502 ms	22136 KB	Output is correct
2	Correct	547 ms	20912 KB	Output is correct
3	Correct	534 ms	20928 KB	Output is correct
4	Correct	473 ms	20856 KB	Output is correct
5	Correct	385 ms	20884 KB	Output is correct

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	553 ms	22776 KB	Output is correct
2	Correct	533 ms	20820 KB	Output is correct
3	Correct	408 ms	20728 KB	Output is correct
4	Correct	463 ms	20728 KB	Output is correct
5	Correct	416 ms	20728 KB	Output is correct

Subtask #16
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	581 ms	25080 KB	Output is correct
2	Correct	686 ms	24024 KB	Output is correct
3	Correct	630 ms	23928 KB	Output is correct
4	Correct	565 ms	24056 KB	Output is correct
5	Correct	455 ms	23928 KB	Output is correct

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	688 ms	25976 KB	Output is correct
2	Correct	630 ms	23800 KB	Output is correct
3	Correct	494 ms	23800 KB	Output is correct
4	Correct	564 ms	23672 KB	Output is correct
5	Correct	456 ms	23672 KB	Output is correct

Subtask #18
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	643 ms	28124 KB	Output is correct
2	Correct	768 ms	26872 KB	Output is correct
3	Correct	710 ms	26616 KB	Output is correct
4	Correct	646 ms	26716 KB	Output is correct
5	Correct	572 ms	26744 KB	Output is correct

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	762 ms	28668 KB	Output is correct
2	Correct	697 ms	26604 KB	Output is correct
3	Correct	560 ms	26648 KB	Output is correct
4	Correct	641 ms	26488 KB	Output is correct
5	Correct	548 ms	26488 KB	Output is correct

Subtask #20
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	871 ms	33984 KB	Output is correct
2	Correct	954 ms	32576 KB	Output is correct
3	Correct	903 ms	32580 KB	Output is correct
4	Correct	824 ms	31856 KB	Output is correct
5	Correct	714 ms	32504 KB	Output is correct

Subtask #21
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1025 ms	33456 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-