oj.uz

Submission #167086

# Submission time Handle Problem Language Result Execution time Memory
167086 2019-12-05T13:52:46 Z dolphingarlic Mobile (BOI12_mobile) C++14
50 / 100
 1000 ms 48336 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-4) {
        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(3) << 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 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 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 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 10 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 12 ms 504 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 636 KB Output is correct
2 Correct 24 ms 632 KB Output is correct
3 Correct 22 ms 636 KB Output is correct
4 Correct 12 ms 632 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 24 ms 632 KB Output is correct
3 Correct 22 ms 624 KB Output is correct
4 Correct 12 ms 632 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 632 KB Output is correct
2 Correct 24 ms 632 KB Output is correct
3 Correct 22 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 260 ms 3912 KB Output is correct
2 Correct 480 ms 4124 KB Output is correct
3 Correct 216 ms 3072 KB Output is correct
4 Correct 183 ms 4088 KB Output is correct
5 Correct 165 ms 2980 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 4192 KB Output is correct
2 Correct 201 ms 3708 KB Output is correct
3 Correct 216 ms 4336 KB Output is correct
4 Correct 210 ms 4216 KB Output is correct
5 Correct 175 ms 4600 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 4652 KB Output is correct
2 Correct 535 ms 4420 KB Output is correct
3 Correct 382 ms 4652 KB Output is correct
4 Correct 127 ms 5112 KB Output is correct
5 Correct 266 ms 4692 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 5216 KB Output is correct
2 Correct 709 ms 5240 KB Output is correct
3 Correct 467 ms 5216 KB Output is correct
4 Correct 128 ms 5112 KB Output is correct
5 Correct 269 ms 5112 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 5340 KB Output is correct
2 Correct 707 ms 5600 KB Output is correct
3 Correct 459 ms 5740 KB Output is correct
4 Correct 131 ms 5624 KB Output is correct
5 Correct 270 ms 5732 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 24696 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 1091 ms 24696 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 1086 ms 29456 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 1080 ms 29356 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 1076 ms 34176 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 34020 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 1059 ms 38844 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 1079 ms 38792 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 1081 ms 48336 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 1086 ms 47308 KB Time limit exceeded
2 Halted 0 ms 0 KB -