oj.uz

Submission #1017120

# Submission time Handle Problem Language Result Execution time Memory
1017120 2024-07-08T21:44:28 Z Keshav211 Mobile (BOI12_mobile) C++14
90 / 100
 1000 ms 51004 KB 
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr){cout<<i<<" ";}cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readundirectedweighted(m) for(ll i=0;i<m;i++){ll a,b,w; cin>>a>>b>>w; a--;b--; adj1[a].pb({b,w});adj1[b].pb({a,w});}
#define readdirectedweighted(m) for(ll i=0;i<m;i++){ll a,b,w; cin>>a>>b>>w; a--;b--; adj1[a].pb({b,w});}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=5e5+1;
const ll graph_size=1e3+2;
const ll mod=1e9+7;
const ld pi=3.141592653589793238462643383279502884197;
const ll large=1e18;
const ll small=-1e18;
// Fast Input/Output
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
    size_t lastSlash=filePath.find_last_of('/');
    size_t lastDot=filePath.rfind('.');
    return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
    if (test){
       return "YES";
    }
    return "NO";
}
ll n,l;
pair<ld,ld> combine(pair<ld,ld> p,pair<ld,ld> q){
    if (q.first<=p.second){
        p.second=q.second;
    }
    return p;
}
// Binary Search
vector<pair<ld,ld>> arr;
bool check(ld radius){
    ld curr=0;
    for (auto i:arr){
        if (radius<i.second){
            continue;
        }
        ld len=sqrt(radius*radius-i.second*i.second);
        ld left=i.first-len;
        ld right=i.first+len;
        if (left<=curr){
            curr=max(curr,right);
        }
    }
    return (curr>=l);
}
// Returns the first value in the range such that check(value)=True.
ld first_true(ld low,ld high){
    while (low+(ld)(1)/(ld)(1e4)<high){
        ld mid=(low+high)/2;
        if (mid<10){
            ll z=1;
        }
        if (check(mid)){
            high=mid;
        }
        else{
            low=mid;
        }
    }
    return low;
}
int main(){
    // auto start_time=chrono::steady_clock::now();
    fastio();
    // str filename=fileio();
    // ifstream cin(filename+".in");
    // ofstream cout(filename+".out");
    ll t=1;
    // cin>>t;
    while (t--){
        cin>>n>>l;
        arr.resize(n);
        for (ll i=0;i<n;i++){
            cin>>arr[i].first>>arr[i].second;
        }
        cout<<setprecision(20)<<first_true(0,1.5*1e9)<<"\n";
    }
    // auto end_time=chrono::steady_clock::now();
    // auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
    // cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}

Compilation message

mobile.cpp: In function 'long double first_true(long double, long double)':
mobile.cpp:94:16: warning: unused variable 'z' [-Wunused-variable]
   94 |             ll z=1;
      |                ^

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2652 KB Output is correct
2 Correct 47 ms 3860 KB Output is correct
3 Correct 27 ms 2768 KB Output is correct
4 Correct 78 ms 3952 KB Output is correct
5 Correct 33 ms 2396 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2908 KB Output is correct
2 Correct 71 ms 2652 KB Output is correct
3 Correct 77 ms 4032 KB Output is correct
4 Correct 79 ms 3932 KB Output is correct
5 Correct 84 ms 4444 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3160 KB Output is correct
2 Correct 43 ms 4192 KB Output is correct
3 Correct 68 ms 3920 KB Output is correct
4 Correct 107 ms 5200 KB Output is correct
5 Correct 68 ms 4184 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3420 KB Output is correct
2 Correct 55 ms 4956 KB Output is correct
3 Correct 49 ms 4596 KB Output is correct
4 Correct 107 ms 5140 KB Output is correct
5 Correct 93 ms 4616 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3420 KB Output is correct
2 Correct 54 ms 4976 KB Output is correct
3 Correct 84 ms 4440 KB Output is correct
4 Correct 103 ms 5200 KB Output is correct
5 Correct 115 ms 4736 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 15964 KB Output is correct
2 Correct 257 ms 23636 KB Output is correct
3 Correct 294 ms 23264 KB Output is correct
4 Correct 547 ms 25448 KB Output is correct
5 Correct 465 ms 22864 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 15960 KB Output is correct
2 Correct 301 ms 22608 KB Output is correct
3 Correct 270 ms 21612 KB Output is correct
4 Correct 497 ms 25428 KB Output is correct
5 Correct 429 ms 23156 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 19036 KB Output is correct
2 Correct 312 ms 28356 KB Output is correct
3 Correct 309 ms 27688 KB Output is correct
4 Correct 685 ms 31016 KB Output is correct
5 Correct 546 ms 27040 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 19032 KB Output is correct
2 Correct 371 ms 26904 KB Output is correct
3 Correct 334 ms 25884 KB Output is correct
4 Correct 601 ms 30800 KB Output is correct
5 Correct 545 ms 27988 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 22364 KB Output is correct
2 Correct 353 ms 33108 KB Output is correct
3 Correct 395 ms 32340 KB Output is correct
4 Correct 745 ms 35664 KB Output is correct
5 Correct 653 ms 31340 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 22364 KB Output is correct
2 Correct 417 ms 31572 KB Output is correct
3 Correct 377 ms 30648 KB Output is correct
4 Correct 720 ms 35536 KB Output is correct
5 Correct 645 ms 32468 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 25432 KB Output is correct
2 Correct 407 ms 37712 KB Output is correct
3 Correct 448 ms 36900 KB Output is correct
4 Correct 808 ms 41044 KB Output is correct
5 Correct 712 ms 36512 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 25432 KB Output is correct
2 Correct 480 ms 35852 KB Output is correct
3 Correct 389 ms 34900 KB Output is correct
4 Correct 853 ms 40872 KB Output is correct
5 Correct 729 ms 37028 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 31576 KB Output is correct
2 Correct 586 ms 47116 KB Output is correct
3 Correct 552 ms 46160 KB Output is correct
4 Execution timed out 1031 ms 50768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 31580 KB Output is correct
2 Correct 555 ms 44888 KB Output is correct
3 Correct 478 ms 44036 KB Output is correct
4 Execution timed out 1016 ms 51004 KB Time limit exceeded
5 Halted 0 ms 0 KB -