# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
623066 | 2022-08-05T06:54:31 Z | 54skyxenon | Mobile (BOI12_mobile) | C++17 | 1000 ms | 48100 KB |
// https://oj.uz/problem/view/BOI12_mobile #include <bits/stdc++.h> using namespace std; #define EPS 0.001 #define CMP_EPS 0.000001 #define pdd pair<double, double> #define mp make_pair int n, l; vector<double> X, Y; vector<pdd> merge(vector<pdd>& intervals) { sort(intervals.begin(), intervals.end()); vector<pdd> new_intervals; for (auto [start, end] : intervals) { if (new_intervals.empty() || new_intervals.back().second < start) { new_intervals.push_back(mp(start, end)); } else { new_intervals.back().second = max(new_intervals.back().second, end); } } return new_intervals; } bool ok(double radius) { vector<pdd> intervals({mp(0, 0), mp(l, l)}); for (int i = 0; i < n; i++) { double x1 = X[i], y1 = Y[i]; double term = (radius * radius) - (y1 * y1); if (term >= 0) { double term_sqrt = sqrt(term); intervals.push_back(mp(x1 - term_sqrt, x1 + term_sqrt)); } } intervals = merge(intervals); for (int i = 0; i < intervals.size() - 1; i++) { double midpt = (intervals[i].second + intervals[i + 1].first) / 2; if (0 <= midpt + CMP_EPS && midpt - CMP_EPS <= l) { return true; } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> l; X.resize(n); Y.resize(n); for (int i = 0; i < n; i++) { cin >> X[i] >> Y[i]; } double lo = 0.0; double hi = l; while (lo + EPS < hi) { double mid = (lo + hi) / 2; if (!ok(mid)) { hi = mid; } else { lo = mid; } } cout << lo << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 340 KB | Output is correct |
2 | Correct | 3 ms | 620 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Incorrect | 5 ms | 340 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 468 KB | Output is correct |
2 | Incorrect | 8 ms | 612 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 468 KB | Output is correct |
2 | Incorrect | 8 ms | 612 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 620 KB | Output is correct |
2 | Incorrect | 8 ms | 612 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 4720 KB | Output is correct |
2 | Incorrect | 237 ms | 4892 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 2700 KB | Output is correct |
2 | Correct | 49 ms | 2580 KB | Output is correct |
3 | Incorrect | 47 ms | 2744 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 251 ms | 5148 KB | Output is correct |
2 | Incorrect | 263 ms | 4972 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 268 ms | 5536 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 326 ms | 5540 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1083 ms | 24340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1095 ms | 24340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1093 ms | 35720 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1092 ms | 35556 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1098 ms | 38736 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1099 ms | 38752 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1097 ms | 41840 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1083 ms | 41836 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1087 ms | 48100 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1095 ms | 48068 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |