oj.uz

Submission #467901

# Submission time Handle Problem Language Result Execution time Memory
467901 2021-08-25T14:01:19 Z kaxzert Mobile (BOI12_mobile) C++17
100 / 100
 823 ms 17312 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 {
        db far = 0;
        fto(i, 1, n) {
            if (mid - eps > a[i].ss) {
                db dis = cal(mid, a[i].ss);
                db left = a[i].ff - dis;
                db right = a[i].ff + dis;
                if (far - eps > left) {
                    far = max(far, right);
                }
            }
        }

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

Subtask #4
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 360 KB Output is correct
4 Correct 4 ms 456 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 400 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 328 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
5 Correct 4 ms 332 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1932 KB Output is correct
2 Correct 69 ms 2252 KB Output is correct
3 Correct 37 ms 1624 KB Output is correct
4 Correct 54 ms 2280 KB Output is correct
5 Correct 31 ms 1476 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1932 KB Output is correct
2 Correct 51 ms 1964 KB Output is correct
3 Correct 58 ms 2332 KB Output is correct
4 Correct 58 ms 2380 KB Output is correct
5 Correct 70 ms 2612 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2120 KB Output is correct
2 Correct 67 ms 2124 KB Output is correct
3 Correct 60 ms 2116 KB Output is correct
4 Correct 79 ms 3004 KB Output is correct
5 Correct 57 ms 2324 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2872 KB Output is correct
2 Correct 77 ms 2760 KB Output is correct
3 Correct 70 ms 2264 KB Output is correct
4 Correct 81 ms 2856 KB Output is correct
5 Correct 70 ms 2752 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2760 KB Output is correct
2 Correct 80 ms 2656 KB Output is correct
3 Correct 67 ms 2372 KB Output is correct
4 Correct 83 ms 2860 KB Output is correct
5 Correct 73 ms 2884 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 9156 KB Output is correct
2 Correct 401 ms 9836 KB Output is correct
3 Correct 385 ms 9764 KB Output is correct
4 Correct 396 ms 9980 KB Output is correct
5 Correct 354 ms 9784 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 10440 KB Output is correct
2 Correct 413 ms 9696 KB Output is correct
3 Correct 353 ms 9760 KB Output is correct
4 Correct 384 ms 9708 KB Output is correct
5 Correct 356 ms 9980 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 10696 KB Output is correct
2 Correct 492 ms 11360 KB Output is correct
3 Correct 488 ms 11416 KB Output is correct
4 Correct 497 ms 11360 KB Output is correct
5 Correct 415 ms 11336 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 11972 KB Output is correct
2 Correct 488 ms 11468 KB Output is correct
3 Correct 413 ms 11448 KB Output is correct
4 Correct 468 ms 11328 KB Output is correct
5 Correct 416 ms 11256 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 12840 KB Output is correct
2 Correct 593 ms 13128 KB Output is correct
3 Correct 548 ms 12832 KB Output is correct
4 Correct 557 ms 12820 KB Output is correct
5 Correct 474 ms 12996 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 13308 KB Output is correct
2 Correct 563 ms 12920 KB Output is correct
3 Correct 494 ms 12916 KB Output is correct
4 Correct 542 ms 12668 KB Output is correct
5 Correct 486 ms 12612 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 14340 KB Output is correct
2 Correct 649 ms 14308 KB Output is correct
3 Correct 618 ms 13764 KB Output is correct
4 Correct 620 ms 13928 KB Output is correct
5 Correct 551 ms 13828 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 14472 KB Output is correct
2 Correct 638 ms 13852 KB Output is correct
3 Correct 563 ms 13960 KB Output is correct
4 Correct 617 ms 13764 KB Output is correct
5 Correct 566 ms 13968 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 17312 KB Output is correct
2 Correct 806 ms 17244 KB Output is correct
3 Correct 788 ms 17032 KB Output is correct
4 Correct 777 ms 16012 KB Output is correct
5 Correct 706 ms 16852 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 17272 KB Output is correct
2 Correct 782 ms 16936 KB Output is correct
3 Correct 726 ms 16912 KB Output is correct
4 Correct 787 ms 16456 KB Output is correct
5 Correct 713 ms 16972 KB Output is correct