Mex (lib/algorithm/mex.hpp)

• View this file on GitHub
• Last update: 2025-06-12 06:47:50+09:00
• Include: #include "lib/algorithm/mex.hpp"

Verified with

• test/yukicoder/0715.test.cpp

Code

#pragma once
#include <algorithm>
#include <iterator>
#include <vector>

/// @brief Mex
struct minimum_excluded {
    minimum_excluded() : n(), _size(), exists(64), v() {}

    constexpr int operator()() const noexcept { return n; }
    constexpr int get() const noexcept { return n; }

    void add(int x) {
        if (x < 0) return;
        ++_size;
        if (_size == (int)exists.size()) {
            exists.resize(_size << 1);
            std::erase_if(v, [&](int y) {
                if (y < (int)exists.size()) {
                    if (exists[y]) --_size;
                    else exists[y] = true;
                    return true;
                }
                return false;
            });
        }
        if (x < (int)exists.size()) {
            if (exists[x]) --_size;
            else exists[x] = true;
        } else {
            v.emplace_back(x);
        }
        while (exists[n]) ++n;
    }

  private:
    int n, _size;
    std::vector<bool> exists;
    std::vector<int> v;
};

#line 2 "lib/algorithm/mex.hpp"
#include <algorithm>
#include <iterator>
#include <vector>

/// @brief Mex
struct minimum_excluded {
    minimum_excluded() : n(), _size(), exists(64), v() {}

    constexpr int operator()() const noexcept { return n; }
    constexpr int get() const noexcept { return n; }

    void add(int x) {
        if (x < 0) return;
        ++_size;
        if (_size == (int)exists.size()) {
            exists.resize(_size << 1);
            std::erase_if(v, [&](int y) {
                if (y < (int)exists.size()) {
                    if (exists[y]) --_size;
                    else exists[y] = true;
                    return true;
                }
                return false;
            });
        }
        if (x < (int)exists.size()) {
            if (exists[x]) --_size;
            else exists[x] = true;
        } else {
            v.emplace_back(x);
        }
        while (exists[n]) ++n;
    }

  private:
    int n, _size;
    std::vector<bool> exists;
    std::vector<int> v;
};

Back to top page