Submission #471406

# Submission time Handle Problem Language Result Execution time Memory
471406 2021-09-09T03:41:00 Z XII Mobile (BOI12_mobile) C++17
100 / 100
611 ms 21912 KB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "BOI12_mobile"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

double SQ(const double &x){
    return x * x;
}

const ll NONE = -2e18;

ll Round(const double &x){
    return (x * 1000 + 0.5);
}

double firstTrue(double lo, double hi, function<bool(double)> f){
    while(Round(lo) < Round(hi)){
        double mid = lo + (hi - lo) / 2;
        if(f(mid)) hi = mid;
        else lo = mid;
    }
    return hi;
}

int main(){
    IOS;
    Fi();
    int n, l; cin >> n >> l;
    vector<int> x(n), y(n);
    FOR(i, 0, n) cin >> x[i] >> y[i];

    const auto check = [&](const double &r) -> bool{
        double L = NONE, R = NONE;
//        vector<pair<double, double>> range;
        FOR(i, 0, n) if(abs(y[i]) <= r){
            double D = sqrt(SQ(r) - SQ(y[i]));
//            range.eb(x[i] - D, x[i] + D);
            if(L == NONE && R == NONE){
                if(x[i] - D <= 0 && 0 <= x[i] + D){
                    L = x[i] - D;
                    R = x[i] + D;
                }
            } else{
                L = min(L, x[i] - D);
                if(x[i] - D <= R) R = max(R, x[i] + D);
            }
        }
//        sort(ALL(range));
//        double L = range[0].fi, R = range[0].se;
//        FOR(i, 1, range.size()){
//            if(range[i].fi <= R) R = max(R, range[i].se);
//        }
        return (L <= 0 && l <= R);
    };


    cout << fixed << setprecision(3) << firstTrue(0, 3e9, check);

    return 0;
}

Compilation message

mobile.cpp: In function 'void Fi()':
mobile.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 416 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 392 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 324 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 3 ms 324 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 44 ms 1604 KB Output is correct
2 Correct 45 ms 1936 KB Output is correct
3 Correct 30 ms 1356 KB Output is correct
4 Correct 38 ms 1996 KB Output is correct
5 Correct 23 ms 1108 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 36 ms 1564 KB Output is correct
2 Correct 35 ms 1612 KB Output is correct
3 Correct 37 ms 1972 KB Output is correct
4 Correct 36 ms 2080 KB Output is correct
5 Correct 47 ms 2448 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 48 ms 1680 KB Output is correct
2 Correct 49 ms 2124 KB Output is correct
3 Correct 46 ms 1856 KB Output is correct
4 Correct 44 ms 3004 KB Output is correct
5 Correct 42 ms 1932 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 61 ms 2636 KB Output is correct
2 Correct 62 ms 2500 KB Output is correct
3 Correct 59 ms 2112 KB Output is correct
4 Correct 44 ms 3008 KB Output is correct
5 Correct 47 ms 2224 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 63 ms 2500 KB Output is correct
2 Correct 63 ms 2500 KB Output is correct
3 Correct 53 ms 2132 KB Output is correct
4 Correct 51 ms 3008 KB Output is correct
5 Correct 47 ms 2372 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 280 ms 8556 KB Output is correct
2 Correct 308 ms 11936 KB Output is correct
3 Correct 328 ms 11436 KB Output is correct
4 Correct 216 ms 12732 KB Output is correct
5 Correct 228 ms 11036 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 336 ms 12416 KB Output is correct
2 Correct 340 ms 10824 KB Output is correct
3 Correct 292 ms 9972 KB Output is correct
4 Correct 217 ms 13544 KB Output is correct
5 Correct 222 ms 11500 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 330 ms 10236 KB Output is correct
2 Correct 400 ms 13448 KB Output is correct
3 Correct 359 ms 13680 KB Output is correct
4 Correct 263 ms 12544 KB Output is correct
5 Correct 280 ms 12712 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 380 ms 13528 KB Output is correct
2 Correct 398 ms 12856 KB Output is correct
3 Correct 324 ms 11892 KB Output is correct
4 Correct 282 ms 11552 KB Output is correct
5 Correct 269 ms 13716 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 389 ms 11832 KB Output is correct
2 Correct 427 ms 14088 KB Output is correct
3 Correct 430 ms 14184 KB Output is correct
4 Correct 289 ms 13084 KB Output is correct
5 Correct 316 ms 14816 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 439 ms 13484 KB Output is correct
2 Correct 452 ms 14100 KB Output is correct
3 Correct 375 ms 13304 KB Output is correct
4 Correct 342 ms 11820 KB Output is correct
5 Correct 313 ms 12868 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 478 ms 13608 KB Output is correct
2 Correct 490 ms 13848 KB Output is correct
3 Correct 497 ms 13824 KB Output is correct
4 Correct 376 ms 12868 KB Output is correct
5 Correct 364 ms 13260 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 503 ms 13120 KB Output is correct
2 Correct 503 ms 14080 KB Output is correct
3 Correct 441 ms 16068 KB Output is correct
4 Correct 345 ms 21912 KB Output is correct
5 Correct 341 ms 18084 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 556 ms 16040 KB Output is correct
2 Correct 609 ms 14148 KB Output is correct
3 Correct 591 ms 13892 KB Output is correct
4 Correct 425 ms 17180 KB Output is correct
5 Correct 448 ms 14132 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 601 ms 12952 KB Output is correct
2 Correct 611 ms 14148 KB Output is correct
3 Correct 556 ms 14572 KB Output is correct
4 Correct 424 ms 16720 KB Output is correct
5 Correct 441 ms 13892 KB Output is correct