oj.uz

Submission #951253

# Submission time Handle Problem Language Result Execution time Memory
951253 2024-03-21T13:46:55 Z seriouslyFlawed Mobile (BOI12_mobile) C++17
100 / 100
 660 ms 52236 KB 
//#pragma GCC optimize("03,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

// Shortcuts for common operations
#define pb push_back
#define p push
#define ppb pop_back
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define ll long long
//#define int ll
#define endl "\n"
#define sz(x) (int)x.size()

// Type definitions for convenience
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vi> vvi;
typedef vector<pii> vii;

// Debugging macros
#define debug(x) cerr << #x << " = " << (x) << '\n'
#define debug_vector(v) _debug_vector(#v, v)
template<typename T>
void _debug_vector(const string& name, const vector<T>& a) {
    cerr << name << " = [ ";
    for(const auto &x : a) cerr << x << ' ';
    cerr << "]\n";
}

// I/O redirection for local testing
#define iofile(io) \
        freopen((io + ".in").c_str(), "r", stdin); \
        freopen((io + ".out").c_str(), "w", stdout);

// delta for floodfill
vi dx = {0, 1, 0, -1};
vi dy = {1, 0, -1, 0};

// extended deltas for floodfill
vi edx = {0, 1, 0, -1, 1, 1, -1, -1};
vi edy = {1, 0, -1, 0, 1, -1, 1, -1};

// Common outputs
void yes() { cout << "YES" << '\n'; }
void no() { cout << "NO" << '\n'; }

#define ld long double
vector<pair<ld, ld>> tab;
int n;
ld l;
ld eps = 0.000001;


bool check(ld alpha){
    ld curr = 0; 

    for(int i = 0; i < n; i++){
        auto [x, y] = tab[i];
        if(abs(y) > alpha) continue;
        ld delta = sqrt(alpha*alpha - y*y);
        if(x - delta <= curr) curr = max(curr, x + delta);
    }

    return (curr >= l);
}


void fx() {
    cin >> n >> l;

    for(int i = 0; i < n; i++){
        pair<ld, ld>curr;
        cin >> curr.f >> curr.s;
        tab.pb(curr);
    }

    ld lo = 0;
    ld hi = 1e10; 
    
    for(int iter = 0; iter < 45; iter++){
        ld mid = (lo + hi)/2;
        if(check(mid)) hi = mid;
        else lo = mid;
    }

    cout << fixed << setprecision(8) << lo << endl;

}

signed main() {

    cin.tie(0)->sync_with_stdio(0);
    // Uncomment the following lines for file I/O
    // iofile(string("hello"));
    
    // Uncomment the following lines for multiple test cases
    // int t; cin >> t; while(t--) fx();
    
    // Single test case
    fx();
    
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 460 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 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 640 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 468 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 3 ms 900 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Correct 4 ms 864 KB Output is correct
5 Correct 4 ms 892 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5600 KB Output is correct
2 Correct 47 ms 6772 KB Output is correct
3 Correct 32 ms 3032 KB Output is correct
4 Correct 47 ms 6504 KB Output is correct
5 Correct 29 ms 3032 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5944 KB Output is correct
2 Correct 46 ms 7360 KB Output is correct
3 Correct 49 ms 5928 KB Output is correct
4 Correct 47 ms 6092 KB Output is correct
5 Correct 49 ms 7592 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6552 KB Output is correct
2 Correct 54 ms 5332 KB Output is correct
3 Correct 52 ms 5800 KB Output is correct
4 Correct 62 ms 5428 KB Output is correct
5 Correct 50 ms 6400 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5324 KB Output is correct
2 Correct 62 ms 5120 KB Output is correct
3 Correct 65 ms 6088 KB Output is correct
4 Correct 59 ms 4824 KB Output is correct
5 Correct 54 ms 6404 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5096 KB Output is correct
2 Correct 67 ms 7124 KB Output is correct
3 Correct 60 ms 7000 KB Output is correct
4 Correct 59 ms 6344 KB Output is correct
5 Correct 62 ms 6604 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 17840 KB Output is correct
2 Correct 328 ms 17748 KB Output is correct
3 Correct 323 ms 17776 KB Output is correct
4 Correct 315 ms 18080 KB Output is correct
5 Correct 299 ms 22940 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 17752 KB Output is correct
2 Correct 366 ms 21436 KB Output is correct
3 Correct 300 ms 21784 KB Output is correct
4 Correct 302 ms 25572 KB Output is correct
5 Correct 284 ms 24104 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 33956 KB Output is correct
2 Correct 409 ms 41236 KB Output is correct
3 Correct 427 ms 41592 KB Output is correct
4 Correct 340 ms 42360 KB Output is correct
5 Correct 356 ms 42564 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 34220 KB Output is correct
2 Correct 410 ms 39336 KB Output is correct
3 Correct 391 ms 41404 KB Output is correct
4 Correct 356 ms 45716 KB Output is correct
5 Correct 370 ms 42096 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 35412 KB Output is correct
2 Correct 444 ms 39892 KB Output is correct
3 Correct 457 ms 40648 KB Output is correct
4 Correct 428 ms 42352 KB Output is correct
5 Correct 444 ms 41904 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 35284 KB Output is correct
2 Correct 493 ms 40164 KB Output is correct
3 Correct 433 ms 41640 KB Output is correct
4 Correct 430 ms 45120 KB Output is correct
5 Correct 429 ms 41220 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 35400 KB Output is correct
2 Correct 561 ms 41880 KB Output is correct
3 Correct 517 ms 39836 KB Output is correct
4 Correct 469 ms 43752 KB Output is correct
5 Correct 449 ms 42668 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 33668 KB Output is correct
2 Correct 523 ms 40072 KB Output is correct
3 Correct 455 ms 40004 KB Output is correct
4 Correct 469 ms 44992 KB Output is correct
5 Correct 431 ms 41904 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 34748 KB Output is correct
2 Correct 615 ms 44692 KB Output is correct
3 Correct 589 ms 44512 KB Output is correct
4 Correct 562 ms 46484 KB Output is correct
5 Correct 552 ms 45252 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 35252 KB Output is correct
2 Correct 644 ms 42420 KB Output is correct
3 Correct 543 ms 44816 KB Output is correct
4 Correct 565 ms 52236 KB Output is correct
5 Correct 542 ms 46464 KB Output is correct