oj.uz

Submission #91793

# Submission time Handle Problem Language Result Execution time Memory
91793 2018-12-30T03:03:05 Z updown1 Mobile (BOI12_mobile) C++17
100 / 100
 597 ms 43232 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;
///500,000,000
int N, L;
pair<int, int> pts[MAXN];
pair<double, double> rng[MAXN];

bool full(double rr) {
    /// make the ranges
    ffi {
        int x = pts[i].a, y = pts[i].b;
        if ((ll)y*y > (long double)rr*rr) {rng[i] = mp(0, 0); continue;}
        double a = sqrt((long double)rr*rr-(long double)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;
	    int x = pts[i].a, y = pts[i].b;
	    double use1 = sqrt((long double)x*x+(long double)y*y);
	    double use2 = sqrt((long double)(x-L)*(x-L)+(long double)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:50: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 3 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 2 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 3 ms 376 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2168 KB Output is correct
2 Correct 39 ms 2168 KB Output is correct
3 Correct 21 ms 2168 KB Output is correct
4 Correct 29 ms 3064 KB Output is correct
5 Correct 14 ms 1912 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2168 KB Output is correct
2 Correct 24 ms 2076 KB Output is correct
3 Correct 27 ms 2296 KB Output is correct
4 Correct 32 ms 2172 KB Output is correct
5 Correct 36 ms 2424 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2424 KB Output is correct
2 Correct 42 ms 2296 KB Output is correct
3 Correct 33 ms 3192 KB Output is correct
4 Correct 44 ms 3548 KB Output is correct
5 Correct 28 ms 3320 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2696 KB Output is correct
2 Correct 52 ms 2772 KB Output is correct
3 Correct 37 ms 3556 KB Output is correct
4 Correct 46 ms 3624 KB Output is correct
5 Correct 34 ms 3576 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2808 KB Output is correct
2 Correct 48 ms 2680 KB Output is correct
3 Correct 36 ms 3584 KB Output is correct
4 Correct 45 ms 3576 KB Output is correct
5 Correct 34 ms 3548 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 12024 KB Output is correct
2 Correct 255 ms 12152 KB Output is correct
3 Correct 240 ms 12920 KB Output is correct
4 Correct 217 ms 13004 KB Output is correct
5 Correct 181 ms 13000 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 12152 KB Output is correct
2 Correct 305 ms 13560 KB Output is correct
3 Correct 194 ms 13560 KB Output is correct
4 Correct 214 ms 13476 KB Output is correct
5 Correct 179 ms 13656 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 14588 KB Output is correct
2 Correct 353 ms 14532 KB Output is correct
3 Correct 280 ms 15864 KB Output is correct
4 Correct 264 ms 15992 KB Output is correct
5 Correct 203 ms 16012 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 14428 KB Output is correct
2 Correct 343 ms 15864 KB Output is correct
3 Correct 220 ms 15864 KB Output is correct
4 Correct 258 ms 15824 KB Output is correct
5 Correct 216 ms 15864 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 16908 KB Output is correct
2 Correct 366 ms 16764 KB Output is correct
3 Correct 342 ms 18168 KB Output is correct
4 Correct 338 ms 18168 KB Output is correct
5 Correct 251 ms 18252 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 16868 KB Output is correct
2 Correct 408 ms 18172 KB Output is correct
3 Correct 285 ms 18260 KB Output is correct
4 Correct 337 ms 18296 KB Output is correct
5 Correct 276 ms 18168 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 19192 KB Output is correct
2 Correct 403 ms 19064 KB Output is correct
3 Correct 412 ms 20728 KB Output is correct
4 Correct 383 ms 20664 KB Output is correct
5 Correct 306 ms 20516 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 19256 KB Output is correct
2 Correct 482 ms 20728 KB Output is correct
3 Correct 338 ms 20600 KB Output is correct
4 Correct 370 ms 20656 KB Output is correct
5 Correct 316 ms 20624 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 23872 KB Output is correct
2 Correct 584 ms 23928 KB Output is correct
3 Correct 476 ms 25336 KB Output is correct
4 Correct 468 ms 23800 KB Output is correct
5 Correct 412 ms 25208 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 23920 KB Output is correct
2 Correct 554 ms 37240 KB Output is correct
3 Correct 409 ms 36316 KB Output is correct
4 Correct 445 ms 43232 KB Output is correct
5 Correct 415 ms 38764 KB Output is correct