shogo-library

競技プログラミング用の C++ ライブラリ

View the Project on GitHub shogo314/shogo-library

:heavy_check_mark: test/unittest/interval-set.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// IntervalSet を「各整数点が覆われているか」の配列による愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <optional>
#include <random>
#include <utility>
#include <vector>

#include "../../src/data_structures/interval-set.hpp"

// 座標 [LO, HI) の範囲で操作する (負の座標も使う)
constexpr int LO = -5, HI = 20;

// 覆われている点の極大な連続部分を半開区間の列にする (接する区間はまとめられる)
std::vector<std::pair<long long, long long>> runs(const std::vector<bool>& cov) {
    std::vector<std::pair<long long, long long>> res;
    for (int i = 0; i < (int)cov.size();) {
        if (!cov[i]) {
            i++;
            continue;
        }
        int j = i;
        while (j < (int)cov.size() && cov[j]) j++;
        res.push_back({i + LO, j + LO});
        i = j;
    }
    return res;
}

int main() {
    std::mt19937 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 2000 && ok; rep++) {
        IntervalSet<long long> st;
        std::vector<bool> cov(HI - LO, false);
        for (int t = 0; t < 30 && ok; t++) {
            long long l = LO + rng() % (HI - LO - 1);
            long long r = l + 1 + rng() % (HI - l - 1 + 1);
            if (r > HI) r = HI;
            if (rng() % 3 != 0) {
                st.insert(l, r);
                for (long long x = l; x < r; x++) cov[x - LO] = true;
            } else {
                st.erase(l, r);
                for (long long x = l; x < r; x++) cov[x - LO] = false;
            }
            auto expect = runs(cov);
            if (st.to_vector() != expect || st.size() != expect.size()) ok = false;

            // covered_by(k): k を含む区間
            for (long long k = LO; k < HI; k++) {
                std::optional<std::pair<long long, long long>> e;
                for (auto& iv : expect) {
                    if (iv.first <= k && k < iv.second) e = iv;
                }
                if (st.covered_by(k) != e) ok = false;
            }
            // covered_by(l, r): [l, r) を完全に含む区間
            for (long long a = LO; a < HI; a++) {
                for (long long b = a + 1; b <= HI; b++) {
                    std::optional<std::pair<long long, long long>> e;
                    for (auto& iv : expect) {
                        if (iv.first <= a && b <= iv.second) e = iv;
                    }
                    if (st.covered_by(a, b) != e) ok = false;
                }
            }
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}
#line 1 "test/unittest/interval-set.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// IntervalSet を「各整数点が覆われているか」の配列による愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <optional>
#include <random>
#include <utility>
#include <vector>

#line 2 "src/data_structures/interval-set.hpp"

/**
 * @file interval-set.hpp
 * @brief 半開区間の集合
 */

#include <cassert>
#include <cstddef>
#include <functional>
#line 12 "src/data_structures/interval-set.hpp"
#include <iterator>
#include <limits>
#line 15 "src/data_structures/interval-set.hpp"
#include <set>
#include <type_traits>
#line 19 "src/data_structures/interval-set.hpp"
/**
 * @brief 半開区間を管理する
 * @tparam T スカラー
 */
template <typename T = long long, class Compare = std::less<T>, std::enable_if_t<std::is_scalar_v<T>>* = nullptr>
struct IntervalSet {
   public:
    using key_type = T;
    using value_type = std::pair<key_type, key_type>;
    inline constexpr static auto key_comp = Compare();
    struct value_compare {
        bool operator()(const value_type& a, const value_type& b) const {
            return key_comp(a.first, b.first) or (not key_comp(b.first, a.first) and key_comp(b.second, a.second));
        }
    };
    inline constexpr static auto value_comp = value_compare();

   private:
    std::set<value_type, value_compare> data;
    using iterator = typename decltype(data)::iterator;
    std::optional<std::pair<iterator, iterator>> find(key_type l, key_type r) const {
        auto itr_l = data.upper_bound({l, l});
        if (itr_l == data.begin()) {
        } else {
            if (not key_comp(std::prev(itr_l)->second, l)) {
                --itr_l;
            }
        }
        if (itr_l == data.end() or key_comp(r, itr_l->first)) {
            return {};
        }
        auto itr_r = data.upper_bound({r, r});
        return std::pair<iterator, iterator>{itr_l, itr_r};
    }

   public:
    IntervalSet() = default;
    /**
     * @brief k が含まれている区間
     */
    std::optional<value_type> covered_by(key_type k) const {
        auto itr = data.upper_bound({k, k});
        if (itr == data.begin()) return {};
        --itr;
        if (key_comp(k, itr->second)) {
            return *itr;
        }
        return {};
    }
    /**
     * @brief [l,r) が完全に含まれている区間
     */
    std::optional<value_type> covered_by(key_type l, key_type r) const {
        auto opt = find(l, r);
        if (not opt.has_value()) {
            return {};
        }
        std::pair<iterator, iterator> p = opt.value();
        if (p.first != std::prev(p.second)) {
            return {};
        }
        if (key_comp(l, p.first->first)) return {};
        if (key_comp(p.first->second, r)) return {};
        return value_type(p.first->first, p.first->second);
    }
    void insert(key_type l, key_type r) {
        assert(key_comp(l, r));
        auto opt = find(l, r);
        if (not opt.has_value()) {
            data.emplace(l, r);
            return;
        }
        auto [itr_l, itr_r] = opt.value();
        if (key_comp(itr_l->first, l)) l = itr_l->first;
        if (key_comp(r, std::prev(itr_r)->second)) r = std::prev(itr_r)->second;
        data.erase(itr_l, itr_r);
        data.emplace(l, r);
    }
    void erase(key_type l, key_type r) {
        assert(key_comp(l, r));
        auto opt = find(l, r);
        if (not opt.has_value()) {
            return;
        }
        auto [itr_l, itr_r] = opt.value();
        std::vector<value_type> tmp;
        if (key_comp(itr_l->first, l)) tmp.push_back({itr_l->first, l});
        if (key_comp(r, std::prev(itr_r)->second)) tmp.push_back({r, std::prev(itr_r)->second});
        data.erase(itr_l, itr_r);
        while (not tmp.empty()) {
            data.insert(tmp.back());
            tmp.pop_back();
        }
    }
    std::size_t size() const {
        return data.size();
    }
    std::vector<value_type> to_vector() const {
        return std::vector<value_type>(data.begin(), data.end());
    }
};
#line 13 "test/unittest/interval-set.test.cpp"

// 座標 [LO, HI) の範囲で操作する (負の座標も使う)
constexpr int LO = -5, HI = 20;

// 覆われている点の極大な連続部分を半開区間の列にする (接する区間はまとめられる)
std::vector<std::pair<long long, long long>> runs(const std::vector<bool>& cov) {
    std::vector<std::pair<long long, long long>> res;
    for (int i = 0; i < (int)cov.size();) {
        if (!cov[i]) {
            i++;
            continue;
        }
        int j = i;
        while (j < (int)cov.size() && cov[j]) j++;
        res.push_back({i + LO, j + LO});
        i = j;
    }
    return res;
}

int main() {
    std::mt19937 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 2000 && ok; rep++) {
        IntervalSet<long long> st;
        std::vector<bool> cov(HI - LO, false);
        for (int t = 0; t < 30 && ok; t++) {
            long long l = LO + rng() % (HI - LO - 1);
            long long r = l + 1 + rng() % (HI - l - 1 + 1);
            if (r > HI) r = HI;
            if (rng() % 3 != 0) {
                st.insert(l, r);
                for (long long x = l; x < r; x++) cov[x - LO] = true;
            } else {
                st.erase(l, r);
                for (long long x = l; x < r; x++) cov[x - LO] = false;
            }
            auto expect = runs(cov);
            if (st.to_vector() != expect || st.size() != expect.size()) ok = false;

            // covered_by(k): k を含む区間
            for (long long k = LO; k < HI; k++) {
                std::optional<std::pair<long long, long long>> e;
                for (auto& iv : expect) {
                    if (iv.first <= k && k < iv.second) e = iv;
                }
                if (st.covered_by(k) != e) ok = false;
            }
            // covered_by(l, r): [l, r) を完全に含む区間
            for (long long a = LO; a < HI; a++) {
                for (long long b = a + 1; b <= HI; b++) {
                    std::optional<std::pair<long long, long long>> e;
                    for (auto& iv : expect) {
                        if (iv.first <= a && b <= iv.second) e = iv;
                    }
                    if (st.covered_by(a, b) != e) ok = false;
                }
            }
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}
Back to top page