Submission #1197709

#TimeUsernameProblemLanguageResultExecution timeMemory
1197709cpismylifeOwOMobile (BOI12_mobile)C++20
25 / 100
1097 ms31868 KiB
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; const int MaxN = 1e6 + 5; int n; long double l; pair<long double, long double> arr[MaxN]; void Inp() { cin >> n >> l; for (int x = 1; x <= n; x++) { cin >> arr[x].first >> arr[x].second; } sort(arr + 1, arr + n + 1); } int i; pair<long double, long double> st[MaxN]; bool Check(long double k) { i = -1; for (int x = 1; x <= n; x++) { if (arr[x].second > k) { continue; } long double p = sqrt(k * k - arr[x].second * arr[x].second), l = arr[x].first - p, r = arr[x].first + p; while (i >= 0 && max(l, st[i].first) <= min(r, st[i].second)) { l = min(l, st[i].first); r = max(r, st[i].second); i--; } i++; st[i] = make_pair(l, r); } for (int x = 0; x <= i; x++) { if (st[x].first <= 0 && l <= st[x].second) { return true; } } return false; } void Exc() { long long l = 0, r = 1e13, mid, res = 1e10; while (l <= r) { mid = (l + r) / 2; if (Check((long double)mid / 1000.0)) { res = mid; r = mid - 1; } else { l = mid + 1; } } cout << fixed << setprecision(3) << (long double)res / 1000.0; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int test = 1; //cin >> test; for (int x = 1; x <= test; x++) { Inp(); Exc(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...