oj.uz

Submission #91788

# Submission time Handle Problem Language Result Execution time Memory
91788 2018-12-30T02:56:40 Z updown1 Mobile (BOI12_mobile) C++17
95 / 100
 1000 ms 33984 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(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

# 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 2 ms 376 KB Output is correct
4 Correct 4 ms 504 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 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

# 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 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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