oj.uz

Submission #467899

# Submission time Handle Problem Language Result Execution time Memory
467899 2021-08-25T13:55:38 Z kaxzert Mobile (BOI12_mobile) C++17
100 / 100
 932 ms 19780 KB 
/**
      00  00      11      00  00  111111  00000  111111  000000
      00 00      1111      0000      11   00     11  11  000000
      0000      11  11      00      11    00000  111111    00
      00 00    11111111    0000    11     00     11 11     00
      00  00  11      11  00  00  111111  00000  11  11    00
**/

#include<bits/stdc++.h>

using namespace std;

void setIO(string s) {
    freopen((s+".inp").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

void setIOusaco(string s) {
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define fast ios::sync_with_stdio(false); cin.tie(0)

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

#define eps 0.000000000001

db cal(db mid, db height) {
    return sqrt(mid*mid - height*height);
}

#define maxN 1000008

pair<db, db> a[maxN];

int main() {
    fast;
    int n;
    db mx;
    cin >> n >> mx;
    fto(i, 1, n) {
        cin >> a[i].ff >> a[i].ss;
        a[i].ss = abs(a[i].ss);
    }

    auto check = [=](db mid) -> bool {
        int pos = 0;
        db far = 0;
        fto(i, 1, n) {
            if (mid - eps > a[i].ss) {
                db dis = cal(mid, a[i].ss);
                if (a[i].ff-dis < -eps && ckmax(far, a[i].ff+dis)) {
                    pos = i;
                }
            }
        }
        if (pos == 0) return 0;
        far = a[pos].ff + cal(mid, a[pos].ss);
        fto(i, pos+1, n) {
            if (mid-eps > a[i].ss) {
                db dis = cal(mid, a[i].ss);
                if (far - eps > a[i].ff+dis || a[i].ff - dis - eps > far) continue;
                far = a[i].ff + dis;
            }
        }

        return (far - eps > mx);
    };

    db left = 1, right = 1.5e9;
    db ans;

    while(right-left > 1e-3) {
        db mid = (left+right)/2;
        if (check(mid)) {
            ans = mid;
            right = mid;
        } else left = mid;
    }

    cout << fixed << setprecision(4) << ans << '\n';

    return 0;
}

Compilation message

mobile.cpp: In function 'void setIO(std::string)':
mobile.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen((s+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp: In function 'void setIOusaco(std::string)':
mobile.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 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 0 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# 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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 4 ms 380 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2260 KB Output is correct
2 Correct 63 ms 2224 KB Output is correct
3 Correct 38 ms 1696 KB Output is correct
4 Correct 57 ms 2236 KB Output is correct
5 Correct 33 ms 1352 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2192 KB Output is correct
2 Correct 49 ms 2108 KB Output is correct
3 Correct 57 ms 2356 KB Output is correct
4 Correct 58 ms 2244 KB Output is correct
5 Correct 67 ms 2420 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2336 KB Output is correct
2 Correct 68 ms 2504 KB Output is correct
3 Correct 74 ms 2484 KB Output is correct
4 Correct 80 ms 3084 KB Output is correct
5 Correct 61 ms 2372 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2768 KB Output is correct
2 Correct 104 ms 2884 KB Output is correct
3 Correct 70 ms 2880 KB Output is correct
4 Correct 79 ms 3084 KB Output is correct
5 Correct 73 ms 2568 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 2788 KB Output is correct
2 Correct 86 ms 2812 KB Output is correct
3 Correct 82 ms 2836 KB Output is correct
4 Correct 78 ms 3164 KB Output is correct
5 Correct 70 ms 2556 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 9832 KB Output is correct
2 Correct 406 ms 9624 KB Output is correct
3 Correct 401 ms 9664 KB Output is correct
4 Correct 390 ms 9664 KB Output is correct
5 Correct 363 ms 9780 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 10568 KB Output is correct
2 Correct 491 ms 9616 KB Output is correct
3 Correct 350 ms 9700 KB Output is correct
4 Correct 383 ms 9564 KB Output is correct
5 Correct 362 ms 9540 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 11532 KB Output is correct
2 Correct 501 ms 11332 KB Output is correct
3 Correct 484 ms 11200 KB Output is correct
4 Correct 512 ms 11360 KB Output is correct
5 Correct 428 ms 11228 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 12200 KB Output is correct
2 Correct 606 ms 11232 KB Output is correct
3 Correct 433 ms 11328 KB Output is correct
4 Correct 483 ms 11232 KB Output is correct
5 Correct 428 ms 11228 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 13788 KB Output is correct
2 Correct 590 ms 12696 KB Output is correct
3 Correct 578 ms 12740 KB Output is correct
4 Correct 563 ms 12856 KB Output is correct
5 Correct 493 ms 12900 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 13928 KB Output is correct
2 Correct 678 ms 12264 KB Output is correct
3 Correct 501 ms 11856 KB Output is correct
4 Correct 553 ms 11516 KB Output is correct
5 Correct 492 ms 11516 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 13180 KB Output is correct
2 Correct 654 ms 13100 KB Output is correct
3 Correct 622 ms 17144 KB Output is correct
4 Correct 635 ms 17108 KB Output is correct
5 Correct 579 ms 17184 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 13296 KB Output is correct
2 Correct 771 ms 16964 KB Output is correct
3 Correct 579 ms 16908 KB Output is correct
4 Correct 651 ms 16836 KB Output is correct
5 Correct 581 ms 16836 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 16272 KB Output is correct
2 Correct 839 ms 16324 KB Output is correct
3 Correct 770 ms 19780 KB Output is correct
4 Correct 782 ms 16016 KB Output is correct
5 Correct 728 ms 19400 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 16360 KB Output is correct
2 Correct 932 ms 19208 KB Output is correct
3 Correct 732 ms 19144 KB Output is correct
4 Correct 798 ms 18072 KB Output is correct
5 Correct 737 ms 18872 KB Output is correct