cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc236_e.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc236/tasks/abc236_e"
#define ERROR 0.001

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Template/FloatingNumberAlias.hpp"
#include "../../Src/Template/Input.hpp"
#include "../../Src/Template/Output.hpp"
#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Utility/BinarySearch.hpp"

#include <vector>
#include <array>
#include <utility>
#include <algorithm>

using namespace zawa;

template <class T>
T eval(const std::vector<T>& A) {
    std::array<T, 2> dp{ T{}, T{} };
    for (auto a : A) {
        std::array<T, 2> nxt{ T{}, T{} };
        nxt[0] = std::max(dp[0] + a, dp[1] + a);
        nxt[1] = dp[0];
        dp = std::move(nxt);
    }
    return std::max(dp[0], dp[1]);
}

int main() {
    SetPrecision(5);
    usize N; input(N);
    std::vector<i32> A(N); input(A);

    auto ave{[&](ld v) -> bool {
        std::vector<ld> B(N);
        for (u32 i{} ; i < N ; i++) B[i] = (ld)A[i] - v;
        return eval(B) >= 0.0l;
    }};

    auto med{[&](i32 v) -> bool {
        std::vector<i32> B(N);
        for (u32 i{} ; i < N ; i++) B[i] = (A[i] >= v ? 1 : -1);
        return eval(B) > 0;
    }};

    out(BinarySearch(0.0l, 1e9 + 1.0l, ave, 50));
    out(BinarySearch(0, (i32)1e9 + 1, med));
}
#line 1 "Test/AtCoder/abc236_e.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc236/tasks/abc236_e"
#define ERROR 0.001

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Template/FloatingNumberAlias.hpp"

namespace zawa {

using ld = long double;

} // namespace zawa
#line 2 "Src/Template/Input.hpp"

#line 2 "Src/Template/ArrayIO.hpp"

#line 4 "Src/Template/ArrayIO.hpp"

#include <iostream>
#include <array>

namespace zawa {

template <class T, usize N>
std::istream &operator>>(std::istream& is, std::array<T, N>& A) {
    for (T& a : A) {
        is >> a;
    }
    return is;
}

template <class T, usize N>
std::ostream &operator<<(std::ostream& os, const std::array<T, N>& A) {
    for (u32 i{} ; i < A.size() ; i++) {
        os << A[i] << (i + 1 == A.size() ? "" : " ");
    }
    return os;
}

} // namespace zawa
#line 2 "Src/Template/VectorIO.hpp"

#line 4 "Src/Template/VectorIO.hpp"

#line 6 "Src/Template/VectorIO.hpp"
#include <vector>

namespace zawa {

template <class T>
std::istream &operator>>(std::istream& is, std::vector<T>& A) {
    for (T& a : A) {
        is >> a;
    }
    return is;
}

template <class T>
std::ostream &operator<<(std::ostream& os, const std::vector<T>& A) {
    for (u32 i{} ; i < A.size() ; i++) {
        os << A[i] << (i + 1 == A.size() ? "" : " ");
    }
    return os;
}

} // namespace zawa
#line 2 "Src/Template/PairIO.hpp"

#line 4 "Src/Template/PairIO.hpp"

#line 6 "Src/Template/PairIO.hpp"
#include <utility>

namespace zawa {

template <class T1, class T2>
std::istream &operator>>(std::istream& is, std::pair<T1, T2>& P) {
    is >> P.first >> P.second;
    return is;
}

template <class T1, class T2>
std::ostream &operator<<(std::ostream& os, const std::pair<T1, T2>& P) {
    os << '(' << P.first << ',' << P.second << ')';
    return os;
}

} // namespace zawa
#line 6 "Src/Template/Input.hpp"

#line 8 "Src/Template/Input.hpp"

namespace zawa {

template <class T>
void input(T& value) {
    std::cin >> value;
}

template <class Head, class... Tail>
void input(Head& head, Tail&... tail) {
    input(head);
    input(tail...);
}

} // namespace zawa
#line 2 "Src/Template/Output.hpp"

#line 6 "Src/Template/Output.hpp"

#line 8 "Src/Template/Output.hpp"

namespace zawa {

void out() {
    std::cout << std::endl;
}

template <class T>
void out(const T& value) {
    std::cout << value << std::endl;
}

template <class Head, class... Tail>
void out(const Head& head, const Tail&... tail) {
    std::cout << head;
    if (sizeof...(tail)) {
        std::cout << ' ';
    }
    out(tail...);
}

void eout() {
    std::cerr << std::endl;
}

template <class T>
void eout(const T& value) {
    std::cerr << value << std::endl;
}

template <class Head, class... Tail>
void eout(const Head& head, const Tail&... tail) {
    std::cerr << head;
    if (sizeof...(tail)) {
        std::cerr << ' ';
    }
    eout(tail...);
}

} // namespace zawa
#line 2 "Src/Template/IOSetting.hpp"

#line 4 "Src/Template/IOSetting.hpp"

#line 6 "Src/Template/IOSetting.hpp"
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Utility/BinarySearch.hpp"

#line 4 "Src/Utility/BinarySearch.hpp"

#include <cmath>
#include <functional>
#include <type_traits>
#line 9 "Src/Utility/BinarySearch.hpp"

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa
#line 10 "Test/AtCoder/abc236_e.test.cpp"

#line 14 "Test/AtCoder/abc236_e.test.cpp"
#include <algorithm>

using namespace zawa;

template <class T>
T eval(const std::vector<T>& A) {
    std::array<T, 2> dp{ T{}, T{} };
    for (auto a : A) {
        std::array<T, 2> nxt{ T{}, T{} };
        nxt[0] = std::max(dp[0] + a, dp[1] + a);
        nxt[1] = dp[0];
        dp = std::move(nxt);
    }
    return std::max(dp[0], dp[1]);
}

int main() {
    SetPrecision(5);
    usize N; input(N);
    std::vector<i32> A(N); input(A);

    auto ave{[&](ld v) -> bool {
        std::vector<ld> B(N);
        for (u32 i{} ; i < N ; i++) B[i] = (ld)A[i] - v;
        return eval(B) >= 0.0l;
    }};

    auto med{[&](i32 v) -> bool {
        std::vector<i32> B(N);
        for (u32 i{} ; i < N ; i++) B[i] = (A[i] >= v ? 1 : -1);
        return eval(B) > 0;
    }};

    out(BinarySearch(0.0l, 1e9 + 1.0l, ave, 50));
    out(BinarySearch(0, (i32)1e9 + 1, med));
}
Back to top page