Submission #1093051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1093051	2024-09-25T18:45:59 Z	TommasoUlian	Mobile (BOI12_mobile)	C++14	0 / 100	766 ms	49128 KB

mobile

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#ifndef ONLINE_JUDGE
#define DEBUG(x) cout << #x << " = " << (x) << endl
#else
#define DEBUG(x)
#endif
#define FOR(n) for(int i = 0; i < (n); i++)
#define SORTA(v) sort((v).begin(), (v).end())
#define SORTD(v) sort((v).rbegin(), (v).rend())
#define PRINT(v) for(auto x: (v))cout << x << " "; cout << endl;
#define TWO(n) (1 << (n))
#define INPUT(v) for(auto &x : (v))cin >> x;

typedef long long ll;

using namespace std;

vector<pair<double, double>> torri;
ll n, L;

bool good(double r) {
    queue<pair<double, double>> s;
    
    for (auto a : torri) {
        double x = a.first, y = a.second;
        if (abs(y) <= r - 1e-6) {
            // Calculate the horizontal range covered by the tower at radius r
            double dx = sqrt((r + y) * (r - y));
            s.push({x - dx, x + dx});
        }
    }
    
    double curr = 0;
    while (!s.empty()) {
        if (curr >= L) return true;
        auto seg = s.front();
        s.pop();
        if (seg.first <= curr) {
            curr = max(seg.second, curr);
        } else {
            return false;
        }
    }
    
    return curr >= L;
}

void solve() {
    cin >> n >> L;
    torri = vector<pair<double, double>>(n);
    for (int i = 0; i < n; i++) {
        cin >> torri[i].first >> torri[i].second;
    }

    double l = 0, r = 2e9;  // Adjust upper bound based on problem limits
    double ans = r;

    while (r - l >= 1e-6) {  // Adjust precision here for better accuracy
        double c = (r + l) / 2;
        if (good(c)) {
            ans = c;
            r = c;
        } else {
            l = c;
        }
    }

    cout << ans << endl;
}

int main() {
    cout << setprecision(18);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    return 0;
}

Subtask #1
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	600 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Incorrect	3 ms	604 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	4108 KB	Output is correct
2	Incorrect	57 ms	4256 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	5280 KB	Output is correct
2	Incorrect	71 ms	5192 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	20764 KB	Output is correct
2	Correct	362 ms	24268 KB	Output is correct
3	Correct	346 ms	23812 KB	Output is correct
4	Incorrect	205 ms	25956 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	357 ms	24848 KB	Output is correct
2	Incorrect	372 ms	23168 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	442 ms	25184 KB	Output is correct
2	Incorrect	421 ms	29052 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	435 ms	29452 KB	Output is correct
2	Incorrect	452 ms	27676 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	504 ms	29044 KB	Output is correct
2	Incorrect	522 ms	33804 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	536 ms	34732 KB	Output is correct
2	Incorrect	503 ms	32216 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	585 ms	33112 KB	Output is correct
2	Incorrect	614 ms	38580 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	612 ms	39364 KB	Output is correct
2	Incorrect	562 ms	36692 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	752 ms	41196 KB	Output is correct
2	Incorrect	766 ms	48144 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	765 ms	49128 KB	Output is correct
2	Incorrect	707 ms	45704 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Submission #1093051

Compilation message