oj.uz

Submission #916401

# Submission time Handle Problem Language Result Execution time Memory
916401 2024-01-25T19:42:18 Z asdasdqwer Mobile (BOI12_mobile) C++14
0 / 100
 1000 ms 83072 KB 
#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;
                continue;
            }

            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;

        double e=0.0;

        for (auto &x:start) {
            if (x[0] <= e && x[1] > e) {
                e=x[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";
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:123: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]
  123 |             while (v.size() != 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 Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 10 ms 1036 KB Output is correct
3 Correct 4 ms 868 KB Output is correct
4 Incorrect 2 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 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 116 ms 10188 KB Output is correct
2 Correct 142 ms 10460 KB Output is correct
3 Correct 85 ms 7212 KB Output is correct
4 Incorrect 31 ms 4052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 10928 KB Output is correct
2 Correct 171 ms 11484 KB Output is correct
3 Correct 92 ms 11916 KB Output is correct
4 Incorrect 31 ms 4056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7500 KB Output is correct
2 Correct 179 ms 11704 KB Output is correct
3 Correct 108 ms 11532 KB Output is correct
4 Incorrect 31 ms 4204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 48448 KB Output is correct
2 Correct 835 ms 49124 KB Output is correct
3 Correct 761 ms 48264 KB Output is correct
4 Incorrect 150 ms 17864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 49020 KB Output is correct
2 Incorrect 231 ms 42312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 70356 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 1010 ms 71692 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 1010 ms 72936 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 1008 ms 72792 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 1031 ms 77644 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 1026 ms 75828 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 1031 ms 82332 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 1037 ms 83072 KB Time limit exceeded
2 Halted 0 ms 0 KB -