oj.uz

Submission #86942

# Submission time Handle Problem Language Result Execution time Memory
86942 2018-11-28T16:42:15 Z popovicirobert Mobile (BOI12_mobile) C++14
38 / 100
 732 ms 132096 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const double eps = 1e-9;
const double INF = 1e18;
const int MAXN = (int) 1e6;

struct Point {
    double x, y;
}pts[MAXN + 1];

inline double dist(Point a, Point b) {
    return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

struct Data {
    double l, r;
    int id;
};

vector <Data> stk;

inline bool eq(double a, double b) {
    return fabs(a - b) < eps;
}

double L;

inline bool ok(double &l, double &r, Point b) {
    Point a = pts[stk.back().id];
    if(eq(a.x, b.x)) {
        return 0;
    }
    double x = 1.0 * (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * (b.x - a.x));
    if(x > L) {
        return 0;
    }
    if(dist(b, {stk.back().l, 0}) - dist(a, {stk.back().l, 0}) < 0) {
        l = stk.back().l;
        r = L;
        return 1;
    }
    if(x - stk.back().l > 0) {
        stk.back().r = x;
        l = x;
        r = L;
        return 0;
    }
    l = stk.back().l;
    r = L;
    return 1;
}

int main() {
    //ifstream cin("B.in");
    //ofstream cout("B.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n >> L;
    for(i = 1; i <= n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }
    stk.push_back({0, L, 1});
    for(i = 2; i <= n; i++) {
        double l = INF, r = -INF;
        while(!stk.empty()) {
            if(ok(l, r, pts[i])) {
                stk.pop_back();
            }
            else {
                break;
            }
        }
        if(r - l > 0) {
            stk.push_back({l, r, i});
        }
    }
    double ans = 0;
    for(auto it : stk) {
        ans = max(ans, dist(pts[it.id], {it.l, 0}));
        ans = max(ans, dist(pts[it.id], {it.r, 0}));
    }
    cout << fixed << setprecision(20) << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 564 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 656 KB Output is correct
2 Correct 5 ms 828 KB Output is correct
3 Correct 6 ms 828 KB Output is correct
4 Correct 5 ms 880 KB Output is correct

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1028 KB Output is correct
2 Correct 7 ms 1208 KB Output is correct
3 Correct 4 ms 1208 KB Output is correct
4 Correct 6 ms 1208 KB Output is correct
5 Incorrect 4 ms 1288 KB Output isn't correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3388 KB Output is correct
2 Correct 52 ms 4308 KB Output is correct
3 Correct 33 ms 4632 KB Output is correct
4 Correct 51 ms 6020 KB Output is correct
5 Incorrect 39 ms 6036 KB Output isn't correct

Subtask #8
0 / 5.0

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

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11236 KB Output is correct
2 Correct 59 ms 11236 KB Output is correct
3 Correct 53 ms 11824 KB Output is correct
4 Correct 81 ms 12328 KB Output is correct
5 Correct 51 ms 13056 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 14748 KB Output is correct
2 Correct 74 ms 16212 KB Output is correct
3 Correct 59 ms 17516 KB Output is correct
4 Correct 89 ms 19084 KB Output is correct
5 Correct 69 ms 20448 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 22868 KB Output is correct
2 Correct 73 ms 23336 KB Output is correct
3 Correct 67 ms 24680 KB Output is correct
4 Correct 75 ms 26288 KB Output is correct
5 Correct 73 ms 27592 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 50608 KB Output is correct
2 Correct 429 ms 50608 KB Output is correct
3 Correct 439 ms 53072 KB Output is correct
4 Correct 366 ms 62668 KB Output is correct
5 Correct 351 ms 69544 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 77436 KB Output is correct
2 Correct 317 ms 78272 KB Output is correct
3 Correct 286 ms 79072 KB Output is correct
4 Correct 396 ms 79072 KB Output is correct
5 Correct 337 ms 79072 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 103696 KB Output is correct
2 Correct 410 ms 103696 KB Output is correct
3 Correct 382 ms 103696 KB Output is correct
4 Correct 465 ms 108992 KB Output is correct
5 Correct 424 ms 117028 KB Output is correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 117028 KB Output is correct
2 Correct 417 ms 125796 KB Output is correct
3 Runtime error 347 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
4 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 449 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 503 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 522 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 589 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 578 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 732 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -