test/unittest/mex-update.test.cpp

• View this file on GitHub
• Last update: 2026-10-13 06:02:01+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• 1点更新・全体の mex 取得 (src/data_structures/mex-update.hpp)

Code

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

// MexUpdate を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "../../src/data_structures/mex-update.hpp"

// v に含まれない最小の非負整数
template <typename T>
T naive_mex(const std::vector<T>& v) {
    std::set<T> s(v.begin(), v.end());
    T x = 0;
    while (s.count(x)) x++;
    return x;
}

template <typename T>
bool run(std::mt19937& rng) {
    for (int rep = 0; rep < 2000; rep++) {
        int n = rng() % 8 + 1;
        // 範囲外の値 (負の値や n より大きい値) も混ぜる
        auto random_value = [&]() -> T { return static_cast<T>(static_cast<int>(rng() % (n + 6)) - 3); };
        std::vector<T> v;
        MexUpdate<T> mu;
        if (rep % 2 == 0) {
            // MexUpdate(n): 値はどれも mex に影響しない値で初期化される
            mu = MexUpdate<T>(n);
            v.assign(n, -1);
            if (mu.prod() != 0) return false;
        } else {
            v.resize(n);
            for (auto& x : v) x = random_value();
            mu = MexUpdate<T>(v);
        }
        if (mu.prod() != naive_mex(v)) return false;
        for (int t = 0; t < 20; t++) {
            int k = rng() % n;
            T x = random_value();
            mu.set(k, x);
            v[k] = x;
            if (mu.prod() != naive_mex(v)) return false;
        }
    }
    return true;
}

int main() {
    std::mt19937 rng(314);
    bool ok = run<int>(rng) && run<long long>(rng);
    // 0..n-1 がすべて揃うと mex は n
    MexUpdate<int> full(std::vector<int>{2, 0, 1});
    ok = ok && full.prod() == 3;
    full.set(1, 3);
    ok = ok && full.prod() == 0;
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}

#line 1 "test/unittest/mex-update.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// MexUpdate を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <random>
#include <set>
#include <vector>

#line 2 "src/data_structures/mex-update.hpp"

/**
 * @file mex-update.hpp
 * @brief 1点更新・全体の mex 取得
 */

#include <cassert>
#include <limits>
#include <map>
#line 13 "src/data_structures/mex-update.hpp"

template <typename T>
struct MexUpdate {
    using value_type = T;

   private:
    inline constexpr static value_type e = std::numeric_limits<value_type>::max();

    int n;
    std::vector<value_type> v;
    std::set<int> s;
    std::map<int, size_t> m;

   public:
    MexUpdate() = default;
    MexUpdate(int n) : n(n), v(n, e) {
        assert(n > 0);
        assert(n + 1 < e);
        std::set<int>::iterator hint = s.end();
        for (int i = n; i >= 0; --i) {
            hint = s.emplace_hint(hint, i);
        }
    }
    MexUpdate(const std::vector<value_type>& init) : n(init.size()), v(init) {
        assert(n > 0);
        assert(n + 1 < e);
        std::set<int>::iterator hint = s.end();
        for (int i = n; i >= 0; --i) {
            hint = s.emplace_hint(hint, i);
        }
        for (const auto& i : init) {
            if (0 <= i and i <= n) {
                m[i]++;
                s.erase(i);
            }
        }
    }
    void set(int k, const value_type& x) {
        assert(0 <= k and k < n);
        if (0 <= v[k] and v[k] <= n) {
            int v_k = v[k];
            auto itr = m.find(v_k);
            if (itr->second > 1) {
                itr->second--;
            } else {
                m.erase(itr);
                s.insert(v_k);
            }
        }
        if (0 <= x and x <= n) {
            int xx = x;
            auto itr = m.find(xx);
            if (itr == m.end()) {
                m[xx]++;
                s.erase(xx);
            } else {
                itr->second++;
            }
        }
        v[k] = x;
    }
    value_type prod() const {
        return *s.begin();
    }
};
#line 12 "test/unittest/mex-update.test.cpp"

// v に含まれない最小の非負整数
template <typename T>
T naive_mex(const std::vector<T>& v) {
    std::set<T> s(v.begin(), v.end());
    T x = 0;
    while (s.count(x)) x++;
    return x;
}

template <typename T>
bool run(std::mt19937& rng) {
    for (int rep = 0; rep < 2000; rep++) {
        int n = rng() % 8 + 1;
        // 範囲外の値 (負の値や n より大きい値) も混ぜる
        auto random_value = [&]() -> T { return static_cast<T>(static_cast<int>(rng() % (n + 6)) - 3); };
        std::vector<T> v;
        MexUpdate<T> mu;
        if (rep % 2 == 0) {
            // MexUpdate(n): 値はどれも mex に影響しない値で初期化される
            mu = MexUpdate<T>(n);
            v.assign(n, -1);
            if (mu.prod() != 0) return false;
        } else {
            v.resize(n);
            for (auto& x : v) x = random_value();
            mu = MexUpdate<T>(v);
        }
        if (mu.prod() != naive_mex(v)) return false;
        for (int t = 0; t < 20; t++) {
            int k = rng() % n;
            T x = random_value();
            mu.set(k, x);
            v[k] = x;
            if (mu.prod() != naive_mex(v)) return false;
        }
    }
    return true;
}

int main() {
    std::mt19937 rng(314);
    bool ok = run<int>(rng) && run<long long>(rng);
    // 0..n-1 がすべて揃うと mex は n
    MexUpdate<int> full(std::vector<int>{2, 0, 1});
    ok = ok && full.prod() == 3;
    full.set(1, 3);
    ok = ok && full.prod() == 0;
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}

Back to top page