Test/AtCoder/abc308_g.test.cpp

View this file on GitHub
Last update: 2024-07-27 05:40:09+09:00
Problem: https://atcoder.jp/contests/abc308/tasks/abc308_g

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc308/tasks/abc308_g"

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

#include <cassert>
#include <iostream>

using namespace zawa;

int main() {
    SetFastIO(); 
    int Q;
    std::cin >> Q;
    SortedAdjacentProduct<XorGroup<int>> data{};
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int x;
            std::cin >> x;
            data.insert(x);
        }
        else if (t == 2) {
            int x;
            std::cin >> x;
            data.erase(x);
        }
        else if (t == 3) {
            std::cout << data.min() << '\n';
        }
        else {
            assert(false);
        }
    }
}

#line 1 "Test/AtCoder/abc308_g.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc308/tasks/abc308_g"

#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/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 6 "Test/AtCoder/abc308_g.test.cpp"

#line 9 "Test/AtCoder/abc308_g.test.cpp"

using namespace zawa;

int main() {
    SetFastIO(); 
    int Q;
    std::cin >> Q;
    SortedAdjacentProduct<XorGroup<int>> data{};
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int x;
            std::cin >> x;
            data.insert(x);
        }
        else if (t == 2) {
            int x;
            std::cin >> x;
            data.erase(x);
        }
        else if (t == 3) {
            std::cout << data.min() << '\n';
        }
        else {
            assert(false);
        }
    }
}