oj.uz

답안 #916412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916412 2024-01-25T20:01:37 Z asdasdqwer Mobile (BOI12_mobile) C++14
100 / 100
 319 ms 28984 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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