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/CF/CF956-F.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/DataStructure/Other/SortedAdjacentProduct.hpp"
#include "../../Src/Utility/BinarySearch.hpp"
#include "../../Src/Algebra/Group/XorGroup.hpp"

#include <iostream>
#include <vector>
using namespace zawa;

long long solve() {
    int N;
    std::cin >> N;
    long long K;
    std::cin >> K;
    std::vector<int> A(N);
    for (auto& a : A) std::cin >> a;
    return BinarySearch(1LL << 32, -1LL, [&](long long v) -> bool {
                SortedAdjacentProduct<XorGroup<int>> data{};
                long long cnt{};
                for (int L{}, R{} ; L < N ; L++) {
                    while (R < N and (data.size() < 2u or data.min() > v)) {
                        data.insert(A[R]);
                        R++;
                    }
                    if (data.size() >= 2u and data.min() <= v) {
                        cnt += N - R + 1;
                    }
                    if (cnt >= K) return true;
                    if (L == R) {
                        R++;
                    }
                    else {
                        data.erase(A[L]);
                    }
                }
                return false;
            });
}

int main() {
#ifdef ONLINE_JUDGE
    SetFastIO();
    int T;
    std::cin >> T;
    while (T--) std::cout << solve() << '\n';
#else
    std::cout << "Hello World" << '\n';
#endif
}
#line 1 "Test/CF/CF956-F.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

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

#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 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#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/DataStructure/Other/SortedAdjacentProduct.hpp"

#include <cassert>
#include <iterator>
#include <set>
#include <utility>

#line 9 "Src/DataStructure/Other/SortedAdjacentProduct.hpp"

namespace zawa {

template <class S>
class SortedAdjacentProduct {
public:
    using V = typename S::Element;
    using Iterator = typename std::multiset<V>::const_iterator;

    SortedAdjacentProduct() = default;

    SortedAdjacentProduct(const SortedAdjacentProduct<S>& sap) 
        : set_{sap.set_}, adj_{sap.adj_} {}

    SortedAdjacentProduct(SortedAdjacentProduct<S>&& sap)
        : set_{std::move(sap.set_)}, adj_{std::move(sap.adj_)} {}

    inline usize size() const noexcept {
        return set_.size();
    }

    inline bool empty() const noexcept {
        return set_.empty();
    }

    const std::multiset<V>& set() const noexcept {
        return set_;
    }

    const std::multiset<V>& adjacents() const noexcept {
        return adj_;
    }

    V min() const noexcept {
        assert(size() >= usize{2});
        return *adj_.cbegin();
    }

    V max() const noexcept {
        assert(size() >= usize(2));
        return *adj_.crbegin();
    }

    void insert(const V& v) {
        Iterator it{set_.lower_bound(v)};
        if (it != set_.end() and it != set_.begin()) {
            V val{S::operation(*std::prev(it), *it)};
            assert(eraseAdj(val));
        }
        if (it != set_.end()) {
            adj_.insert(S::operation(v, *it));
        }
        if (it != set_.begin()) {
            adj_.insert(S::operation(*std::prev(it), v));
        }
        set_.insert(v);
    }

    void erase(const V& v) {
        auto it{set_.lower_bound(v)};
        assert(it != set_.end() and *it == v);
        if (it != set_.begin()) {
            V val{S::operation(*std::prev(it), *it)};
            assert(eraseAdj(val));
        }
        if (std::next(it) != set_.end()) {
            V val{S::operation(*it, *std::next(it))};
            assert(eraseAdj(val));
        }
        if (it != set_.begin() and std::next(it) != set_.end()) {
            V val{S::operation(*std::prev(it), *std::next(it))};
            adj_.insert(val);
        }
        set_.erase(it);
    }

    bool contains(const V& v) {
        return set_.find(v) != set_.end();
    }

private:
    std::multiset<V> set_, adj_;

    bool eraseAdj(const V& v) {
        auto it{adj_.find(v)};
        bool res{it != adj_.end()};
        if (res) adj_.erase(it);
        return res;
    }
};

} // 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 2 "Src/Algebra/Group/XorGroup.hpp"

namespace zawa {

template <class T>
class XorGroup {
public:
    using Element = T;
    static constexpr Element identity() noexcept {
        return Element{};
    }
    static constexpr Element operation(const Element& l, const Element& r) noexcept {
        return l ^ r;
    }
    static constexpr Element inverse(const Element& v) noexcept {
        return v;
    }
};

} // namespace zawa
#line 7 "Test/CF/CF956-F.test.cpp"

#line 9 "Test/CF/CF956-F.test.cpp"
#include <vector>
using namespace zawa;

long long solve() {
    int N;
    std::cin >> N;
    long long K;
    std::cin >> K;
    std::vector<int> A(N);
    for (auto& a : A) std::cin >> a;
    return BinarySearch(1LL << 32, -1LL, [&](long long v) -> bool {
                SortedAdjacentProduct<XorGroup<int>> data{};
                long long cnt{};
                for (int L{}, R{} ; L < N ; L++) {
                    while (R < N and (data.size() < 2u or data.min() > v)) {
                        data.insert(A[R]);
                        R++;
                    }
                    if (data.size() >= 2u and data.min() <= v) {
                        cnt += N - R + 1;
                    }
                    if (cnt >= K) return true;
                    if (L == R) {
                        R++;
                    }
                    else {
                        data.erase(A[L]);
                    }
                }
                return false;
            });
}

int main() {
#ifdef ONLINE_JUDGE
    SetFastIO();
    int T;
    std::cin >> T;
    while (T--) std::cout << solve() << '\n';
#else
    std::cout << "Hello World" << '\n';
#endif
}
Back to top page