Submission #1101158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101158		BLOBVISGOD	Mobile (BOI12_mobile)	C++17	50 / 100	1062 ms	64712 KiB

mobile

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,l; cin >> n >> l;
    vector<array<ll,2>> a(n);
    rep(i,0,n) rep(j,0,2) cin >> a[i][j];
    rep(i,0,n) a[i][1] = a[i][1]*a[i][1];

    double lo = 0, hi = 2e9;
    rep(iter,0,72){
        double mid = (lo+hi)/2, mid2 = mid*mid;
        vector<array<double,2>> segs;
        rep(i,0,n) if (a[i][1] < mid2){
            double d = sqrt(mid2 - a[i][1]);
            segs.push_back({a[i][0]-d,a[i][0]+d});
        }
        sort(all(segs), [&](auto l, auto r){
            return l[1] < r[1];
        });
        double r = 0;
        for(auto [L,R] : segs){
            if (L <= r) r = max(r,R);
        }
        if (r < l) lo = mid;
        else hi = mid;
    }
    cout << setprecision(15) << lo << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5