oj.uz

Submission #467890

# Submission time Handle Problem Language Result Execution time Memory
467890 2021-08-25T13:40:19 Z kaxzert Mobile (BOI12_mobile) C++17
0 / 100
 121 ms 5528 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.0000000001

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) {
            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 = mx;
    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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 6 ms 460 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Incorrect 5 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 2256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 2200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2396 KB Output is correct
2 Correct 66 ms 2744 KB Output is correct
3 Correct 56 ms 2580 KB Output is correct
4 Incorrect 121 ms 3696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 3368 KB Output is correct
2 Correct 85 ms 3288 KB Output is correct
3 Correct 61 ms 2852 KB Output is correct
4 Incorrect 114 ms 3888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3300 KB Output is correct
2 Correct 79 ms 3188 KB Output is correct
3 Correct 72 ms 2940 KB Output is correct
4 Incorrect 120 ms 3780 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 4564 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 72 ms 5432 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 50 ms 4544 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 68 ms 5500 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 49 ms 4620 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 74 ms 5452 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 66 ms 4552 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 66 ms 5528 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 49 ms 4588 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 70 ms 5496 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -