oj.uz

Submission #1023076

# Submission time Handle Problem Language Result Execution time Memory
1023076 2024-07-14T09:19:13 Z tanprodium Mobile (BOI12_mobile) C++14
100 / 100
 654 ms 51028 KB 
// include
#include<bits/stdc++.h>

using namespace std;

// define
#define fi    first
#define se    second

#define pub   push_back
#define pob   pop_back
#define puf   push_front
#define pof   pop_front
#define eb    emplace_back
#define upb   upper_bound
#define lwb   lower_bound

#define left  VAN
#define right TAN

#define sz(a)               (int)a.size()
#define all(a)              (a).begin(),(a).end()
#define rall(a)             (a).begin(),(a).end()
#define sort_and_unique(a)  sort(all(a));(a).resize(unique(all(a))-a.begin())
#define max_                max_element
#define min_                min_element

// another define
using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mil = map<int, ll>;
using mli = map<ll, int>;
using mll = map<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

// random
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// templates
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (y > x) {
            x = y;
            return (true);
        } else return (false);
    }

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (y < x) {
            x = y;
            return (true);
        } else return (false);
    }

template<class T>
    void print(const T &a, const int &l, const int &r) {
        for (int i = l; i <= r; i++)
            cout << a[i] << ' ';
        cout << '\n';
    }

// limit
const int oo = 2e9;
const int N  = 1e6;

// function
void yesno(bool x) {
    cout << (x ? "YES\n" : "NO\n");
}

// mem
ll L;
int n;
ld x[N + 5], y[N + 5];

bool ok(ld d) {
    bool exist = false;
    ld l, r;
    for (int i = 1; i <= n; i++) {
        ld y0 = abs(y[i]);
        if (y0 <= d) {
            ld delta = sqrt(d * d - y0 * y0);
            ld u = x[i] - delta;
            ld v = x[i] + delta;
            if (v >= 0.0) {
                if (!exist) {
                    l = u; r = v;
                    exist = true;
                } else {
                    if (u <= r) {
                        minimize(l, u);
                        maximize(r, v);
                    }
                }
            }
        }
    }
    if (exist && l <= 0.0 && r >= L) return (true);
    else return (false);
}

ld BS() {
    ld l = 0.0, r = 2e9;
    for (int _ = 1; _ <= 42; _++) {
        ld mid = (l + r) / 2;
        if (ok(mid))
            r = mid;
        else l = mid;
    }
    return (r);
}

void solve() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    cout << fixed << setprecision(4) << BS() << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;

    while (t--) solve();
    return 0;
}

Compilation message

mobile.cpp: In function 'bool ok(ld)':
mobile.cpp:107:27: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |     if (exist && l <= 0.0 && r >= L) return (true);
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2904 KB Output is correct
2 Correct 50 ms 2652 KB Output is correct
3 Correct 31 ms 2140 KB Output is correct
4 Correct 39 ms 2652 KB Output is correct
5 Correct 24 ms 1988 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2900 KB Output is correct
2 Correct 34 ms 2628 KB Output is correct
3 Correct 40 ms 2896 KB Output is correct
4 Correct 54 ms 2824 KB Output is correct
5 Correct 42 ms 3164 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3160 KB Output is correct
2 Correct 56 ms 3016 KB Output is correct
3 Correct 47 ms 2904 KB Output is correct
4 Correct 46 ms 3416 KB Output is correct
5 Correct 48 ms 3268 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3412 KB Output is correct
2 Correct 68 ms 3544 KB Output is correct
3 Correct 58 ms 3592 KB Output is correct
4 Correct 48 ms 3412 KB Output is correct
5 Correct 52 ms 3600 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3372 KB Output is correct
2 Correct 69 ms 3576 KB Output is correct
3 Correct 58 ms 3492 KB Output is correct
4 Correct 47 ms 3408 KB Output is correct
5 Correct 51 ms 3420 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 15932 KB Output is correct
2 Correct 327 ms 23632 KB Output is correct
3 Correct 346 ms 23380 KB Output is correct
4 Correct 246 ms 25428 KB Output is correct
5 Correct 260 ms 22704 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 15956 KB Output is correct
2 Correct 342 ms 22776 KB Output is correct
3 Correct 299 ms 21776 KB Output is correct
4 Correct 262 ms 25320 KB Output is correct
5 Correct 252 ms 23232 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 19024 KB Output is correct
2 Correct 414 ms 28500 KB Output is correct
3 Correct 406 ms 27732 KB Output is correct
4 Correct 291 ms 30968 KB Output is correct
5 Correct 303 ms 27156 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 19024 KB Output is correct
2 Correct 373 ms 26960 KB Output is correct
3 Correct 342 ms 26004 KB Output is correct
4 Correct 293 ms 30756 KB Output is correct
5 Correct 296 ms 27744 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 22356 KB Output is correct
2 Correct 474 ms 33136 KB Output is correct
3 Correct 483 ms 32596 KB Output is correct
4 Correct 326 ms 35904 KB Output is correct
5 Correct 363 ms 31608 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 22356 KB Output is correct
2 Correct 425 ms 31588 KB Output is correct
3 Correct 433 ms 30804 KB Output is correct
4 Correct 332 ms 35668 KB Output is correct
5 Correct 344 ms 32336 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 25512 KB Output is correct
2 Correct 570 ms 37716 KB Output is correct
3 Correct 567 ms 36948 KB Output is correct
4 Correct 388 ms 41040 KB Output is correct
5 Correct 416 ms 36692 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 25432 KB Output is correct
2 Correct 546 ms 36068 KB Output is correct
3 Correct 462 ms 35152 KB Output is correct
4 Correct 367 ms 41040 KB Output is correct
5 Correct 380 ms 37200 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 31568 KB Output is correct
2 Correct 647 ms 47188 KB Output is correct
3 Correct 623 ms 46160 KB Output is correct
4 Correct 461 ms 50784 KB Output is correct
5 Correct 464 ms 45136 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 31568 KB Output is correct
2 Correct 566 ms 45088 KB Output is correct
3 Correct 523 ms 43952 KB Output is correct
4 Correct 454 ms 51028 KB Output is correct
5 Correct 458 ms 46672 KB Output is correct