oj.uz

Submission #467896

# Submission time Handle Problem Language Result Execution time Memory
467896 2021-08-25T13:51:42 Z kaxzert Mobile (BOI12_mobile) C++17
50 / 100
 96 ms 3620 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 ldb long 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 100008

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-6) {
        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 324 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 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 328 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 1464 KB Output is correct
2 Correct 67 ms 2468 KB Output is correct
3 Correct 40 ms 1760 KB Output is correct
4 Correct 57 ms 2572 KB Output is correct
5 Correct 32 ms 1368 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1508 KB Output is correct
2 Correct 49 ms 2208 KB Output is correct
3 Correct 57 ms 2504 KB Output is correct
4 Correct 59 ms 2628 KB Output is correct
5 Correct 67 ms 3012 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1676 KB Output is correct
2 Correct 75 ms 1732 KB Output is correct
3 Correct 63 ms 1876 KB Output is correct
4 Correct 79 ms 2308 KB Output is correct
5 Correct 63 ms 2500 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1832 KB Output is correct
2 Correct 84 ms 2100 KB Output is correct
3 Correct 73 ms 2112 KB Output is correct
4 Correct 82 ms 2276 KB Output is correct
5 Correct 71 ms 3088 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 1860 KB Output is correct
2 Correct 88 ms 2040 KB Output is correct
3 Correct 73 ms 2024 KB Output is correct
4 Correct 81 ms 2312 KB Output is correct
5 Correct 72 ms 3048 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 3620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 3536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 3556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 3608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 3520 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 3500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 3520 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 3588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 3572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 3536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -