oj.uz

Submission #91787

# Submission time Handle Problem Language Result Execution time Memory
91787 2018-12-30T02:54:38 Z updown1 Mobile (BOI12_mobile) C++17
90 / 100
 1000 ms 50976 KB 
/*
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(4) <<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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 5 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
5 Correct 4 ms 504 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2776 KB Output is correct
2 Correct 68 ms 2680 KB Output is correct
3 Correct 36 ms 2040 KB Output is correct
4 Correct 52 ms 2724 KB Output is correct
5 Correct 26 ms 1912 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2808 KB Output is correct
2 Correct 44 ms 2728 KB Output is correct
3 Correct 50 ms 2812 KB Output is correct
4 Correct 54 ms 2808 KB Output is correct
5 Correct 63 ms 3100 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3196 KB Output is correct
2 Correct 69 ms 3064 KB Output is correct
3 Correct 55 ms 3064 KB Output is correct
4 Correct 77 ms 3452 KB Output is correct
5 Correct 52 ms 3192 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3448 KB Output is correct
2 Correct 82 ms 3448 KB Output is correct
3 Correct 62 ms 3452 KB Output is correct
4 Correct 77 ms 3576 KB Output is correct
5 Correct 59 ms 3448 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 3448 KB Output is correct
2 Correct 85 ms 3580 KB Output is correct
3 Correct 63 ms 3492 KB Output is correct
4 Correct 76 ms 3452 KB Output is correct
5 Correct 62 ms 3448 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 394 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 16120 KB Output is correct
2 Correct 443 ms 22776 KB Output is correct
3 Correct 335 ms 21880 KB Output is correct
4 Correct 379 ms 25336 KB Output is correct
5 Correct 336 ms 23548 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 19192 KB Output is correct
2 Correct 549 ms 28460 KB Output is correct
3 Correct 492 ms 27896 KB Output is correct
4 Correct 482 ms 31312 KB Output is correct
5 Correct 393 ms 27256 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 19180 KB Output is correct
2 Correct 563 ms 27068 KB Output is correct
3 Correct 398 ms 25976 KB Output is correct
4 Correct 470 ms 30968 KB Output is correct
5 Correct 393 ms 28024 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 22392 KB Output is correct
2 Correct 675 ms 33152 KB Output is correct
3 Correct 601 ms 32632 KB Output is correct
4 Correct 579 ms 35960 KB Output is correct
5 Correct 463 ms 31480 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 22512 KB Output is correct
2 Correct 603 ms 31736 KB Output is correct
3 Correct 483 ms 30712 KB Output is correct
4 Correct 590 ms 35832 KB Output is correct
5 Correct 464 ms 32432 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 25696 KB Output is correct
2 Correct 726 ms 37880 KB Output is correct
3 Correct 691 ms 37240 KB Output is correct
4 Correct 646 ms 41052 KB Output is correct
5 Correct 528 ms 36600 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 26148 KB Output is correct
2 Correct 699 ms 36072 KB Output is correct
3 Correct 557 ms 35064 KB Output is correct
4 Correct 692 ms 41052 KB Output is correct
5 Correct 562 ms 37112 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 33144 KB Output is correct
2 Correct 960 ms 47224 KB Output is correct
3 Correct 910 ms 46304 KB Output is correct
4 Correct 844 ms 50976 KB Output is correct
5 Correct 679 ms 45304 KB Output is correct

Subtask #21
0 / 5.0

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