Submission #916387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916387	2024-01-25T19:26:52 Z	asdasdqwer	Mobile (BOI12_mobile)	C++14	4 / 100	1000 ms	83596 KB

mobile

#pragma GCC optimize("O3")

#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];

    vector<pii> tt;
    for (auto &x:v) {
        if (!tt.size()) {
            tt.push_back(x);
        }

        else if (tt.back()[0] == x[0] && abs(tt.back()[1]) > abs(x[1])) {
            tt.pop_back();
        }
        tt.push_back(x);
    }

    v=tt;
    n=v.size();

    long double l = 1;
    long double r = 1e10;

    cout<<setprecision(15);

    for (auto &x:v) {
        r = min(r, (long double)max(sqrt(x[0]*x[0] + x[1]*x[1]), sqrt((x[0]-t)*(x[0]-t) + x[1]*x[1])));
    }

    // cout<<r<<"\n";

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

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

                    start.push_back(pos1);
                }
            }
    
            i++;
        }

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

        bool possible=true;

        queue<double> ss;

        for (auto &x:start) {
            while (ss.size() && ss.front() >= x[0])ss.pop();

            ss.push(x[1]);
        }

        while (ss.size()) {
            if (ss.front() != t) {
                possible=false;
                break;
            }
            ss.pop();
        }
    
        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
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	3 ms	808 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 ms	676 KB	Output is correct

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	604 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Incorrect	4 ms	988 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	860 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	27 ms	6220 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	2780 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	11084 KB	Output is correct
2	Incorrect	49 ms	10904 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	80 ms	11764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	7348 KB	Output is correct
2	Incorrect	55 ms	11024 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	833 ms	48528 KB	Output is correct
2	Incorrect	254 ms	48232 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	336 ms	48276 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1018 ms	71632 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	433 ms	70496 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1054 ms	73928 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	485 ms	72444 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1045 ms	75172 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	535 ms	77216 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1010 ms	83348 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	641 ms	83596 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #916387

Compilation message