Submission #916281

#	Time	Username	Problem	Language	Result	Execution time	Memory
916281		asdasdqwer	Mobile (BOI12_mobile)	C++14	8 / 100	1094 ms	64852 KiB

mobile

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

#define int int64_t
#define pii array<int,2>

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,t;cin>>n>>t;
    vector<pii> v(n);
    for (auto &x:v)cin>>x[0]>>x[1];

    double l = 1;
    double r = 1e9;
    vector<bool> rem(n, false);

    while (abs(l-r) > 0.0000001) {
        double m = (l+r)/2.0;
        int i=0;
        vector<array<double,2>> start;
        for (auto &x:v) {
            if ((double)abs(x[1]) >= m) {
                rem[i]=true;
            }

            else {
                double aa=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;
                }

                else {
                    pos1[0]=max(pos1[0], 0.0);
                    pos1[1]=min(pos1[1], (double)t);
                    start.push_back(pos1);
                }
            }

            i++;
        }

        start.push_back({0.0, 0.0});
        start.push_back({(double)t,(double)t});

        sort(start.begin(),start.end());
        // cout<<m<<" "<<l<<" "<<r<<"\n";
        // for (auto &x:start) {
        //     cout<<x[0]<<" "<<x[1]<<"\n";
        // }
        // cout<<"\n";

        array<double,2> pos={0.0, 0.0};
        bool possible=true;

        for (auto &x:start) {
            if (x[0] <= pos[1]) {
                pos[1]=max(pos[1], x[1]);
            }

            else {
                possible=false;
                break;
            }
        }

        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 (int i=0;i<n;i++) {
                rem[i]=false;
            }
        }
    }

    cout<<l<<"\n";
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:90:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   90 |             while (v.size() != n){
      |                    ~~~~~~~~~^~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 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