oj.uz

Submission #467897

# Submission time Handle Problem Language Result Execution time Memory
467897 2021-08-25T13:53:18 Z kaxzert Mobile (BOI12_mobile) C++17
80 / 100
 1000 ms 35176 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 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 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-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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 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 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Correct 5 ms 488 KB Output is correct
4 Correct 7 ms 460 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 7 ms 488 KB Output is correct
4 Correct 6 ms 460 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2628 KB Output is correct
2 Correct 98 ms 2716 KB Output is correct
3 Correct 66 ms 1888 KB Output is correct
4 Correct 73 ms 2628 KB Output is correct
5 Correct 41 ms 1876 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2648 KB Output is correct
2 Correct 69 ms 2560 KB Output is correct
3 Correct 89 ms 2756 KB Output is correct
4 Correct 87 ms 2832 KB Output is correct
5 Correct 87 ms 3012 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2948 KB Output is correct
2 Correct 106 ms 2844 KB Output is correct
3 Correct 98 ms 2860 KB Output is correct
4 Correct 96 ms 3496 KB Output is correct
5 Correct 86 ms 3092 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 3452 KB Output is correct
2 Correct 122 ms 3444 KB Output is correct
3 Correct 98 ms 3440 KB Output is correct
4 Correct 98 ms 3448 KB Output is correct
5 Correct 96 ms 3432 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 3352 KB Output is correct
2 Correct 121 ms 3436 KB Output is correct
3 Correct 99 ms 3368 KB Output is correct
4 Correct 95 ms 3328 KB Output is correct
5 Correct 93 ms 3436 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 19212 KB Output is correct
2 Correct 612 ms 20064 KB Output is correct
3 Correct 632 ms 19944 KB Output is correct
4 Correct 489 ms 19964 KB Output is correct
5 Correct 473 ms 20164 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 20064 KB Output is correct
2 Correct 753 ms 20036 KB Output is correct
3 Correct 509 ms 20036 KB Output is correct
4 Correct 486 ms 20060 KB Output is correct
5 Correct 481 ms 20164 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 23196 KB Output is correct
2 Correct 755 ms 23196 KB Output is correct
3 Correct 713 ms 23200 KB Output is correct
4 Correct 599 ms 23156 KB Output is correct
5 Correct 628 ms 23088 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 23200 KB Output is correct
2 Correct 837 ms 23220 KB Output is correct
3 Correct 625 ms 23192 KB Output is correct
4 Correct 599 ms 23196 KB Output is correct
5 Correct 625 ms 23136 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 26232 KB Output is correct
2 Correct 938 ms 25968 KB Output is correct
3 Correct 869 ms 25996 KB Output is correct
4 Correct 697 ms 26048 KB Output is correct
5 Correct 661 ms 25956 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 25952 KB Output is correct
2 Correct 953 ms 26024 KB Output is correct
3 Correct 736 ms 26456 KB Output is correct
4 Correct 719 ms 26484 KB Output is correct
5 Correct 713 ms 26456 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 29952 KB Output is correct
2 Execution timed out 1008 ms 29588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 30236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 35060 KB Output is correct
2 Execution timed out 1088 ms 35176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 35004 KB Time limit exceeded
2 Halted 0 ms 0 KB -