oj.uz

Submission #823232

# Submission time Handle Problem Language Result Execution time Memory
823232 2023-08-12T09:45:41 Z normankr07 Mobile (BOI12_mobile) C++17
100 / 100
 997 ms 35328 KB 
/*
Templete by norman/KNN-07
Who tf even love CP :sob:
*/

#ifndef LOCAL
#pragma GCC optimize("Ofast,unroll-loops,inline")
// Bitwise pragma fuck
// #pragma GCC target("avx,avx2,bmi")

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("arch=skylake")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#endif

#include <bits/stdc++.h>
using namespace std;

// Wish you can debug? YesYes
#ifndef LOCAL
#define cerr \
    if (0)   \
    cerr
#endif

// Policy based DS?
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// Who tf deal with overflow
#define int long long

/*
pbds blog :
https://codeforces.com/blog/entry/11080
https://codeforces.com/blog/entry/13279
*/
// Useful pbds
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template <typename T>
// using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

#define el '\n'
#define mpp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define emp emplace_back
#define fi first
#define nd second
#define forinc(i, a, b) for (int i = (a); i <= (b); i++)
#define fordec(i, a, b) for (int i = (a); i >= (b); i--)
#define alle(x) (x).begin(), (x).end()
#define ralle(x) (x).rbegin(), (x).rend()
#define mms(a, v) memset(a, v, sizeof(a))
#define lwb(a, v) lower_bound((a).begin(), (a).end(), v)
#define upb(a, v) upper_bound((a).begin(), (a).end(), v)
#define bit(i, a) (((a) >> (i)) & 1)

#define BIT_SET(a, b) ((a) |= (1ULL << (b)))
#define BIT_CLEAR(a, b) ((a) &= ~(1ULL << (b)))
#define BIT_FLIP(a, b) ((a) ^= (1ULL << (b)))
#define BIT_CHECK(a, b) (!!((a) & (1ULL << (b))))
#define BITMASK_SET(x, mask) ((x) |= (mask))
#define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
#define BITMASK_FLIP(x, mask) ((x) ^= (mask))
#define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
#define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
#define POPCNT(mask) __builtin_popcount(mask)
#define POPCNTLL(mask) __builtin_popcountll(mask)
#define CTZ(mask) __builtin_ctz(mask)
#define CTZLL(mask) __builtin_ctzll(mask)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef vector<bool> vb;

template <typename T, typename U>
inline void maximize(T &x, U y)
{
    if (y < x)
        x = y;
}
template <typename T, typename U>
inline void minimize(T &x, U y)
{
    if (x < y)
        x = y;
}
inline int add_m(int a, int b, int mod)
{
    int res = a + b;
    return (res >= mod ? res - mod : res);
}
inline int mod_neg(int a, int b, int mod)
{
    int res;
    if (abs(a - b) < mod)
        res = a - b;
    else
        res = (a - b) % mod;
    return (res < 0 ? res + mod : res);
}
inline int mul_wmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return (res >= c ? res % c : res);
}
inline int mul_wnmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return ((res % c) + c) % c;
}

// Debugger Utils
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

template <size_t i, class T>
ostream &print_tuple_utils(ostream &out, const T &tup)
{
    if constexpr (i == tuple_size<T>::value)
        return out << ")";
    else
        return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template <class... U>
ostream &operator<<(ostream &out, const tuple<U...> &t)
{
    return print_tuple_utils<0, tuple<U...>>(out, t);
}
#define db(val) "[" #val " = " << (val) << "] "
// End if debugger utils

namespace Hasher
{
    struct custom_hash
    {
        static uint32_t splitmix64(uint32_t x)
        {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(uint64_t x) const
        {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    struct hash_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = custom_hash{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
    struct hash_pair_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = hash_pair{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
}
using namespace Hasher;

const string taskname = "";
const bool tc = false;

const int oo = 1e9, mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll ool = 1e18;
const ldb eps = 1e-6;
const int MAXN = 1e6;

/*
Author: normankr07
Problem:

Submission links:

Editorial links:

Algorithm:
*/

void solve()
{
    int n, L;
    cin >> n >> L;
    vector<pii> arr(n);
    for (auto &[u, v] : arr)
        cin >> u >> v;
    ldb l = 0, r = 1e10;
    auto check = [&](ldb mid) -> bool
    {
        ldb cur = 0;
        for (const auto &[x, y] : arr)
        {
            ldb diff = sqrtl(mid * mid - y * y);
            if (x - diff <= cur)
                cur = max(cur, x + diff);
        }
        return L <= cur;
    };
    ldb ans = 1;
    while (r - l >= 1e-4)
    {
        ldb mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid;
            ans = mid;
        }
        else
            l = mid;
    }
    cout << fixed << setprecision(6) << ans;
}

int32_t main()
{
    if (fopen((taskname + ".inp").c_str(), "r"))
    {
        freopen((taskname + ".inp").c_str(), "r", stdin);
        freopen((taskname + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tsc = 1;
    if (tc)
    {
        cin >> tsc;
    }
    while (tsc--)
    {
        solve();
        cout << el;
    }
#ifdef LOCAL
    cerr << "\n"
         << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message

mobile.cpp: In function 'int32_t main()':
mobile.cpp:254:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  254 |         freopen((taskname + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:255:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |         freopen((taskname + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1492 KB Output is correct
2 Correct 29 ms 1492 KB Output is correct
3 Correct 23 ms 1748 KB Output is correct
4 Correct 69 ms 2656 KB Output is correct
5 Correct 31 ms 1492 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1492 KB Output is correct
2 Correct 54 ms 1364 KB Output is correct
3 Correct 64 ms 1492 KB Output is correct
4 Correct 67 ms 2772 KB Output is correct
5 Correct 78 ms 3088 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1620 KB Output is correct
2 Correct 28 ms 1620 KB Output is correct
3 Correct 37 ms 2536 KB Output is correct
4 Correct 98 ms 3792 KB Output is correct
5 Correct 63 ms 2608 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1876 KB Output is correct
2 Correct 41 ms 1876 KB Output is correct
3 Correct 44 ms 2916 KB Output is correct
4 Correct 103 ms 3796 KB Output is correct
5 Correct 78 ms 3040 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1876 KB Output is correct
2 Correct 32 ms 1876 KB Output is correct
3 Correct 52 ms 2908 KB Output is correct
4 Correct 98 ms 3804 KB Output is correct
5 Correct 79 ms 3164 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8148 KB Output is correct
2 Correct 167 ms 8148 KB Output is correct
3 Correct 169 ms 15308 KB Output is correct
4 Correct 498 ms 17736 KB Output is correct
5 Correct 444 ms 14924 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 8148 KB Output is correct
2 Correct 353 ms 14680 KB Output is correct
3 Correct 237 ms 13776 KB Output is correct
4 Correct 528 ms 17480 KB Output is correct
5 Correct 430 ms 15432 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 9684 KB Output is correct
2 Correct 198 ms 9684 KB Output is correct
3 Correct 207 ms 18380 KB Output is correct
4 Correct 594 ms 21480 KB Output is correct
5 Correct 492 ms 17644 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 9684 KB Output is correct
2 Correct 431 ms 17640 KB Output is correct
3 Correct 269 ms 16488 KB Output is correct
4 Correct 633 ms 21356 KB Output is correct
5 Correct 535 ms 18412 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 11220 KB Output is correct
2 Correct 228 ms 11220 KB Output is correct
3 Correct 242 ms 21392 KB Output is correct
4 Correct 702 ms 24832 KB Output is correct
5 Correct 559 ms 20236 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 11220 KB Output is correct
2 Correct 497 ms 20480 KB Output is correct
3 Correct 327 ms 19596 KB Output is correct
4 Correct 703 ms 24604 KB Output is correct
5 Correct 587 ms 21324 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 12756 KB Output is correct
2 Correct 261 ms 12756 KB Output is correct
3 Correct 272 ms 24364 KB Output is correct
4 Correct 815 ms 28440 KB Output is correct
5 Correct 661 ms 23960 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12756 KB Output is correct
2 Correct 573 ms 23336 KB Output is correct
3 Correct 353 ms 22352 KB Output is correct
4 Correct 790 ms 28208 KB Output is correct
5 Correct 664 ms 24364 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 15956 KB Output is correct
2 Correct 331 ms 15956 KB Output is correct
3 Correct 337 ms 30448 KB Output is correct
4 Correct 997 ms 35168 KB Output is correct
5 Correct 818 ms 29556 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 15956 KB Output is correct
2 Correct 736 ms 29160 KB Output is correct
3 Correct 457 ms 28388 KB Output is correct
4 Correct 977 ms 35328 KB Output is correct
5 Correct 859 ms 30704 KB Output is correct