oj.uz

Submission #167085

# Submission time Handle Problem Language Result Execution time Memory
167085 2019-12-05T13:49:39 Z dolphingarlic Mobile (BOI12_mobile) C++14
50 / 100
 1000 ms 47736 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#pragma GCC Optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define x first
#define y second
using namespace std;

pair<double, double> p[1000000];
pair<double, int> contacts[2000000];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    double len;
    cin >> n >> len;
    FOR(i, 0, n) cin >> p[i].x >> p[i].y;

    double l = 1, r = 5e8;
    while (r - l > 1e-7) {
        double mid = (l + r) / 2;

        int cnt = 0;
        FOR(i, 0, n) {
            if (mid < abs(p[i].y)) continue;
            double delta = sqrt(mid * mid - p[i].y * p[i].y);
            contacts[cnt++] = {p[i].x - delta, 1};
            contacts[cnt++] = {p[i].x + delta, -1};
        }
        contacts[cnt++] = {0.0, 0};
        contacts[cnt++] = {len, 0};
        sort(contacts, contacts + cnt);

        int active = 0;
        bool good = true;
        FOR(i, 0, cnt) {
            active += contacts[i].y;
            if (contacts[i].x > len) break;
            if (contacts[i].x < 0) continue;
            if (active == 0) {
                good = false;
                break;
            }
        }
        if (good) r = mid;
        else l = mid;
    }

    cout << fixed << setprecision(6) << l;
    return 0;
}

Compilation message

mobile.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")
 
mobile.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct
2 Correct 11 ms 504 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 14 ms 504 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 712 KB Output is correct
2 Correct 28 ms 696 KB Output is correct
3 Correct 26 ms 760 KB Output is correct
4 Correct 13 ms 760 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 632 KB Output is correct
2 Correct 28 ms 504 KB Output is correct
3 Correct 26 ms 632 KB Output is correct
4 Correct 13 ms 672 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 632 KB Output is correct
2 Correct 28 ms 632 KB Output is correct
3 Correct 26 ms 632 KB Output is correct
4 Correct 12 ms 632 KB Output is correct
5 Correct 16 ms 632 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 4188 KB Output is correct
2 Correct 584 ms 4376 KB Output is correct
3 Correct 257 ms 3448 KB Output is correct
4 Correct 175 ms 5240 KB Output is correct
5 Correct 165 ms 3192 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 4444 KB Output is correct
2 Correct 201 ms 4088 KB Output is correct
3 Correct 215 ms 4592 KB Output is correct
4 Correct 182 ms 5368 KB Output is correct
5 Correct 171 ms 5880 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 4900 KB Output is correct
2 Correct 695 ms 4636 KB Output is correct
3 Correct 461 ms 5376 KB Output is correct
4 Correct 129 ms 6904 KB Output is correct
5 Correct 266 ms 5532 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 5588 KB Output is correct
2 Correct 855 ms 6508 KB Output is correct
3 Correct 567 ms 6008 KB Output is correct
4 Correct 132 ms 7096 KB Output is correct
5 Correct 285 ms 6392 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 5472 KB Output is correct
2 Correct 862 ms 6648 KB Output is correct
3 Correct 553 ms 6140 KB Output is correct
4 Correct 134 ms 7080 KB Output is correct
5 Correct 267 ms 6392 KB Output is correct

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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