oj.uz

Submission #167083

# Submission time Handle Problem Language Result Execution time Memory
167083 2019-12-05T13:48:42 Z dolphingarlic Mobile (BOI12_mobile) C++14
8 / 100
 1000 ms 63940 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-5) {
        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 << 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 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 10 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Incorrect 13 ms 632 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 632 KB Output is correct
2 Incorrect 26 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 632 KB Output is correct
2 Incorrect 24 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 632 KB Output is correct
2 Incorrect 25 ms 732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 4620 KB Output is correct
2 Incorrect 523 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 4956 KB Output is correct
2 Correct 198 ms 4572 KB Output is correct
3 Incorrect 212 ms 5296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 5212 KB Output is correct
2 Incorrect 580 ms 5508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 28152 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 1052 ms 32076 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 1077 ms 33684 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 1067 ms 38552 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 1066 ms 39420 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 1078 ms 44852 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 1078 ms 44928 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 1073 ms 51204 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 1052 ms 55988 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 1085 ms 63940 KB Time limit exceeded
2 Halted 0 ms 0 KB -