Submission #916412

#	Time	Username	Problem	Language	Result	Execution time	Memory
916412		asdasdqwer	Mobile (BOI12_mobile)	C++14	100 / 100	319 ms	28984 KiB

mobile

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;

// #define int int64_t
#define pii array<int,2>
#define MAXN 1000001

array<double,2> start[MAXN];
int point=0;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,t;cin>>n>>t;
    vector<pii> v;
    for (int i=0;i<n;i++) {
        int a,b;cin>>a>>b;
        if (v.size() && v.back()[0] == a) {
            if (abs(v.back()[1]) > b) {
                v.pop_back();
                v.push_back({a,b});
            }
        }

        else {
            v.push_back({a,b});
        }
    }

    n=v.size();

    double l = 1;
    double r = 1e10;

    cout<<setprecision(15);

    // vector<bool> rem(n, false);
    // vector<array<double,2>> start;

    while (abs(l-r) > 0.001) {
        point = 0;
        double m = (l+r)/2.0;
        int i=0;
        bool all=false;
        
        for (auto &x:v) {
            if ((double)abs(x[1]) >= m) {
                // rem[i]=true;
                i++;
                continue;
            }

            // if (rem[i]) {
            //     i++;
            //     continue;
            // }
    
            else {
                double aa=(double)abs(x[1]);
                double dis=sqrt(m*m-aa*aa);
                array<double,2> pos1 = {x[0]-dis,x[0]+dis};
                if ((pos1[0] < 0.0 && pos1[1] < 0.0) || (pos1[0] > (double)t && pos1[1] > (double)t)) {
                    // rem[i]=true;
                    i++;
                    continue;
                }
    
                else {
                    pos1[0]=max(pos1[0], 0.0);
                    pos1[1]=min(pos1[1], (double)t);
                    if (pos1[0] == 0.0 && pos1[1] == t) {
                        all=true;
                        break;
                    }

                    start[point++] = pos1;
                }
            }
    
            i++;
        }

        if (all) {
            r=m;
            continue;
        }

        bool possible=true;

        double e=0.0;

        for (int i=0;i<point;i++) {
            if (start[i][0] <= e && start[i][1] > e) {
                e=start[i][1];
            }
        }

        if (e<t) possible=false;
    
        if (possible) {
            r=m;
            // int cnt=0;
            // int pt=0;
            // for (int i=0;i<n;i++) {
            //     if (rem[i]) {
            //         cnt++;
            //     }
                
            //     else if (cnt != 0) {
            //         swap(v[i], v[pt]);
            //     }
    
            //     if (!rem[i]) {
            //         pt++;
            //     }
            // }
    
            // n -= cnt;
    
            // while (v.size() != n){
            //     v.pop_back();
            //     rem.pop_back();
            // }
    
            // for (int i=0;i<n;i++) {
            //     rem[i]=false;
            // }
        }
    
        else {
            l=m;
            // for (i=0;i<n;i++) {
            //     rem[i]=false;
            // }
        }
    }

    cout<<r<<"\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: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5