oj.uz

Submission #916291

# Submission time Handle Problem Language Result Execution time Memory
916291 2024-01-25T15:30:59 Z asdasdqwer Mobile (BOI12_mobile) C++14
8 / 100
 1000 ms 48336 KB 
#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 = 1e15;
    vector<bool> rem(n, false);
    
    while (abs(l-r) > 0.00001) {
        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";
        // for (auto &x:v) {
        //     cout<<x[0]<<" "<<x[1]<<"\n";
        // }
        // cout<<"\n\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;
            }
        }
    }

    r = round(r * 10000.0) / 10000.0;
    cout<<r<<"\n";
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Incorrect 5 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 744 KB Output is correct
2 Incorrect 15 ms 748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 756 KB Output is correct
2 Incorrect 15 ms 748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 748 KB Output is correct
2 Incorrect 15 ms 740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 4912 KB Output is correct
2 Incorrect 367 ms 5184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 5016 KB Output is correct
2 Correct 185 ms 4864 KB Output is correct
3 Incorrect 207 ms 5272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 5308 KB Output is correct
2 Incorrect 394 ms 5528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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