Submission #916412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916412	2024-01-25T20:01:37 Z	asdasdqwer	Mobile (BOI12_mobile)	C++14	100 / 100	319 ms	28984 KB

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.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	468 KB	Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	604 KB	Output is correct
2	Correct	2 ms	604 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 ms	860 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4056 KB	Output is correct
2	Correct	16 ms	4060 KB	Output is correct
3	Correct	13 ms	3548 KB	Output is correct
4	Correct	17 ms	4312 KB	Output is correct
5	Correct	5 ms	856 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1112 KB	Output is correct
2	Correct	12 ms	1760 KB	Output is correct
3	Correct	15 ms	4048 KB	Output is correct
4	Correct	17 ms	4312 KB	Output is correct
5	Correct	19 ms	4308 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	3800 KB	Output is correct
2	Correct	17 ms	4060 KB	Output is correct
3	Correct	15 ms	4044 KB	Output is correct
4	Correct	24 ms	4808 KB	Output is correct
5	Correct	12 ms	1512 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4140 KB	Output is correct
2	Correct	17 ms	4056 KB	Output is correct
3	Correct	12 ms	1884 KB	Output is correct
4	Correct	24 ms	4812 KB	Output is correct
5	Correct	18 ms	4300 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	4568 KB	Output is correct
2	Correct	18 ms	4060 KB	Output is correct
3	Correct	12 ms	1880 KB	Output is correct
4	Correct	26 ms	4824 KB	Output is correct
5	Correct	18 ms	4300 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	15556 KB	Output is correct
2	Correct	70 ms	5124 KB	Output is correct
3	Correct	64 ms	4724 KB	Output is correct
4	Correct	111 ms	14012 KB	Output is correct
5	Correct	86 ms	10432 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	5520 KB	Output is correct
2	Correct	173 ms	14524 KB	Output is correct
3	Correct	65 ms	6856 KB	Output is correct
4	Correct	108 ms	12272 KB	Output is correct
5	Correct	91 ms	10424 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	18992 KB	Output is correct
2	Correct	80 ms	5700 KB	Output is correct
3	Correct	76 ms	5084 KB	Output is correct
4	Correct	130 ms	16516 KB	Output is correct
5	Correct	98 ms	12736 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	6184 KB	Output is correct
2	Correct	201 ms	19784 KB	Output is correct
3	Correct	70 ms	7060 KB	Output is correct
4	Correct	130 ms	16828 KB	Output is correct
5	Correct	108 ms	14724 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	22712 KB	Output is correct
2	Correct	91 ms	6480 KB	Output is correct
3	Correct	86 ms	5868 KB	Output is correct
4	Correct	152 ms	18180 KB	Output is correct
5	Correct	105 ms	9720 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	7032 KB	Output is correct
2	Correct	211 ms	22456 KB	Output is correct
3	Correct	88 ms	8204 KB	Output is correct
4	Correct	151 ms	17772 KB	Output is correct
5	Correct	124 ms	16312 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	26292 KB	Output is correct
2	Correct	102 ms	6980 KB	Output is correct
3	Correct	98 ms	6736 KB	Output is correct
4	Correct	175 ms	20656 KB	Output is correct
5	Correct	137 ms	14524 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	7764 KB	Output is correct
2	Correct	241 ms	24764 KB	Output is correct
3	Correct	103 ms	9024 KB	Output is correct
4	Correct	178 ms	20996 KB	Output is correct
5	Correct	144 ms	17340 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	319 ms	28984 KB	Output is correct
2	Correct	127 ms	8528 KB	Output is correct
3	Correct	122 ms	7876 KB	Output is correct
4	Correct	224 ms	15032 KB	Output is correct
5	Correct	158 ms	8128 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	484 KB	Output is correct
2	Correct	296 ms	20716 KB	Output is correct
3	Correct	126 ms	3984 KB	Output is correct
4	Correct	212 ms	14512 KB	Output is correct
5	Correct	176 ms	11956 KB	Output is correct

Submission #916412

Compilation message