oj.uz

Submission #916306

# Submission time Handle Problem Language Result Execution time Memory
916306 2024-01-25T15:53:55 Z asdasdqwer Mobile (BOI12_mobile) C++14
50 / 100
 1000 ms 75100 KB 
#include <bits/stdc++.h>
using namespace std;

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

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.0001) {
        double m = (l+r)/2.0;
        int i=0;
        vector<array<double,2>> start;
        bool all=false;
        
        for (auto &x:v) {
            if ((double)abs(x[1]) >= m) {
                rem[i]=true;
            }
    
            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;
                }
    
                else {
                    pos1[0]=max(pos1[0], (double)0.0);
                    pos1[1]=min(pos1[1], (double)t);
                    if (pos1[0] == 0.0 && pos1[1] == t) {
                        all=true;
                        for (int j=0;j<i;j++)rem[j]=false;
                        break;
                    }
                    start.push_back(pos1);
                }
            }
    
            i++;
        }

        if (all) {
            r=m;
            continue;
        }
    
        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 (i=0;i<n;i++) {
                rem[i]=false;
            }
        }
    }
    cout<<setprecision(15);
    cout<<r<<"\n";
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:109: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]
  109 |             while (v.size() != n){
      |                    ~~~~~~~~~^~~~

Subtask #1
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 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 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 360 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 6 ms 728 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 604 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 7 ms 788 KB Output is correct
4 Correct 2 ms 608 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 11 ms 1040 KB Output is correct
3 Correct 8 ms 820 KB Output is correct
4 Correct 2 ms 608 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 8 ms 816 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 5756 KB Output is correct
2 Correct 224 ms 9480 KB Output is correct
3 Correct 158 ms 5060 KB Output is correct
4 Correct 28 ms 4072 KB Output is correct
5 Correct 13 ms 2280 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3288 KB Output is correct
2 Correct 26 ms 3812 KB Output is correct
3 Correct 18 ms 4048 KB Output is correct
4 Correct 20 ms 3876 KB Output is correct
5 Correct 24 ms 4228 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 10088 KB Output is correct
2 Correct 273 ms 10840 KB Output is correct
3 Correct 150 ms 6796 KB Output is correct
4 Correct 26 ms 5376 KB Output is correct
5 Correct 19 ms 4188 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 11320 KB Output is correct
2 Correct 327 ms 10652 KB Output is correct
3 Correct 271 ms 9736 KB Output is correct
4 Correct 27 ms 5612 KB Output is correct
5 Correct 25 ms 4952 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 7080 KB Output is correct
2 Correct 329 ms 10264 KB Output is correct
3 Correct 337 ms 9972 KB Output is correct
4 Correct 28 ms 5600 KB Output is correct
5 Correct 23 ms 4820 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 42724 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 1025 ms 44776 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 1014 ms 62308 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 1031 ms 65060 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 1093 ms 65828 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 67720 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 1014 ms 66848 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 1016 ms 69472 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 1018 ms 70744 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 1029 ms 75100 KB Time limit exceeded
2 Halted 0 ms 0 KB -