shogo-library

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

View the Project on GitHub shogo314/shogo-library

:heavy_check_mark: test/unittest/mo.test.cpp

Depends on

Code

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

// Mo を愚直な実装とランダムに比較する
// 左端と右端で別の操作を渡すコンストラクタ (6 引数) を、区間を deque のまま持つ形で確かめる
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <deque>
#include <iostream>
#include <random>
#include <vector>

#include "../../src/others/mo.hpp"

// 区間の要素を順番込みで区別するハッシュ
long long ordered_hash(const std::deque<int>& d) {
    long long h = 0;
    for (int x : d) h = (h * 1000003 + x + 1) % 998244353;
    return h;
}

int main() {
    std::mt19937 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 500 && ok; rep++) {
        int n = rng() % 30 + 1;
        std::vector<int> a(n);
        for (int& x : a) x = rng() % 1000;
        // 左に足すときは先頭、右に足すときは末尾に入れる。左右を取り違えると順番が崩れる
        auto add_left = [&](std::deque<int>& d, int i) { d.push_front(a[i]); };
        auto delete_left = [&](std::deque<int>& d, int i) {
            if (d.front() != a[i]) ok = false;
            d.pop_front();
        };
        auto add_right = [&](std::deque<int>& d, int i) { d.push_back(a[i]); };
        auto delete_right = [&](std::deque<int>& d, int i) {
            if (d.back() != a[i]) ok = false;
            d.pop_back();
        };
        Mo mo(n, std::deque<int>(), add_left, delete_left, add_right, delete_right);
        int q = rng() % 30 + 1;
        std::vector<std::pair<int, int>> qs(q);
        for (auto& [l, r] : qs) {
            l = rng() % (n + 1);
            r = rng() % (n + 1);
            if (l > r) std::swap(l, r);
            mo.query(l, r);
        }
        auto res = mo.solve<long long>([](std::deque<int>& d) { return ordered_hash(d); });
        for (int i = 0; i < q; i++) {
            auto [l, r] = qs[i];
            std::deque<int> expect(a.begin() + l, a.begin() + r);
            if (res[i] != ordered_hash(expect)) ok = false;
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}
#line 1 "test/unittest/mo.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// Mo を愚直な実装とランダムに比較する
// 左端と右端で別の操作を渡すコンストラクタ (6 引数) を、区間を deque のまま持つ形で確かめる
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <deque>
#include <iostream>
#include <random>
#include <vector>

#line 2 "src/others/mo.hpp"

/**
 * @file mo.hpp
 * @brief Mo's algorithm
 */

#line 9 "src/others/mo.hpp"
#include <array>
#include <type_traits>
#include <algorithm>
#include <cmath>

template <typename U, class ADD_LEFT, class DELETE_LEFT, class ADD_RIGHT = ADD_LEFT, class DELETE_RIGHT = DELETE_LEFT>
struct Mo {
   private:
    int _n;
    std::vector<std::array<int, 3>> lri;
    U _e;
    ADD_LEFT _add_left;
    DELETE_LEFT _delete_left;
    ADD_RIGHT _add_right;
    DELETE_RIGHT _delete_right;

    static_assert(std::is_invocable_r_v<void, ADD_LEFT, U&, int>, "ADD_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_LEFT, U&, int>, "DELETE_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, ADD_RIGHT, U&, int>, "ADD_RIGHT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_RIGHT, U&, int>, "DELETE_RIGHT must be callable with (U&, int)");

   public:
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left,
       const ADD_RIGHT& add_right,
       const DELETE_RIGHT& delete_right) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_right), _delete_right(delete_right) {}
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_left), _delete_right(delete_left) {}
    void query(int l, int r) {
        lri.push_back({l, r, (int)lri.size()});
    }
    template <typename T, class F>
    std::vector<T> solve(const F& f) {
        static_assert(std::is_invocable_r_v<T, F, U&>, "The function passed to solve must be callable with (U&) and return T");
        
        const int w = std::max<int>(1, 1.0 * _n / std::max<double>(1.0, std::sqrt(lri.size() * 2.0 / 3.0)));
        std::sort(lri.begin(), lri.end(), [=](const std::array<int, 3>& a, const std::array<int, 3>& b) {
            int aw = a[0] / w;
            int bw = b[0] / w;
            if (aw != bw) return aw < bw;
            if (aw & 1) return a[1] > b[1];
            return a[1] < b[1];
        });
        std::vector<T> res(lri.size());
        long long tmpl = 0, tmpr = 0;
        U tmp = _e;
        for (auto [l, r, i] : lri) {
            while (tmpl > l) {
                tmpl--;
                _add_left(tmp, tmpl);
            }
            while (tmpr < r) {
                _add_right(tmp, tmpr);
                tmpr++;
            }
            while (tmpl < l) {
                _delete_left(tmp, tmpl);
                tmpl++;
            }
            while (tmpr > r) {
                tmpr--;
                _delete_right(tmp, tmpr);
            }
            res[i] = f(tmp);
        }
        return res;
    }
};
#line 13 "test/unittest/mo.test.cpp"

// 区間の要素を順番込みで区別するハッシュ
long long ordered_hash(const std::deque<int>& d) {
    long long h = 0;
    for (int x : d) h = (h * 1000003 + x + 1) % 998244353;
    return h;
}

int main() {
    std::mt19937 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 500 && ok; rep++) {
        int n = rng() % 30 + 1;
        std::vector<int> a(n);
        for (int& x : a) x = rng() % 1000;
        // 左に足すときは先頭、右に足すときは末尾に入れる。左右を取り違えると順番が崩れる
        auto add_left = [&](std::deque<int>& d, int i) { d.push_front(a[i]); };
        auto delete_left = [&](std::deque<int>& d, int i) {
            if (d.front() != a[i]) ok = false;
            d.pop_front();
        };
        auto add_right = [&](std::deque<int>& d, int i) { d.push_back(a[i]); };
        auto delete_right = [&](std::deque<int>& d, int i) {
            if (d.back() != a[i]) ok = false;
            d.pop_back();
        };
        Mo mo(n, std::deque<int>(), add_left, delete_left, add_right, delete_right);
        int q = rng() % 30 + 1;
        std::vector<std::pair<int, int>> qs(q);
        for (auto& [l, r] : qs) {
            l = rng() % (n + 1);
            r = rng() % (n + 1);
            if (l > r) std::swap(l, r);
            mo.query(l, r);
        }
        auto res = mo.solve<long long>([](std::deque<int>& d) { return ordered_hash(d); });
        for (int i = 0; i < q; i++) {
            auto [l, r] = qs[i];
            std::deque<int> expect(a.begin() + l, a.begin() + r);
            if (res[i] != ordered_hash(expect)) ok = false;
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}
Back to top page