test/unit/xor_basis.test.cpp

• View this file on GitHub
• Last update: 2026-10-27 07:17:18+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• Xor Basis (math/xor_basis.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "math/xor_basis.hpp"
int main() {
    std::mt19937_64 rng(20261027);
    for (int iter = 0; iter < 2000; iter++) {
        int n = rng() % 11, bits = 1 + rng() % 10;
        std::set<long long> span{0};
        xor_basis<long long> xb;
        for (int i = 0; i < n; i++) {
            long long x = rng() % (1LL << bits);
            bool in = span.count(x);
            assert(xb.contains(x) == in);
            assert(xb.insert(x) == !in);
            if (!in) {
                std::set<long long> nxt = span;
                for (long long v : span) nxt.insert(v ^ x);
                span = nxt;
            }
        }
        assert((1LL << xb.size()) == (long long)span.size());
        for (long long x = 0; x < (1LL << bits); x++) assert(xb.contains(x) == span.count(x));
        for (int t = 0; t < 5; t++) {
            long long xv = rng() % (1LL << bits);
            std::vector<long long> sorted;
            for (long long v : span) sorted.push_back(v ^ xv);
            std::sort(sorted.begin(), sorted.end());
            assert(xb.min(xv) == sorted.front());
            assert(xb.max(xv) == sorted.back());
            for (int k = 0; k < (int)sorted.size(); k++) {
                assert(xb.kth_smallest(k, xv) == sorted[k]);
                assert(xb.kth_largest(k, xv) == sorted[sorted.size() - 1 - k]);
            }
        }
    }
    {
        // full rank over 63 bits, signed long long
        xor_basis<long long> xb;
        for (int i = 0; i < 63; i++) assert(xb.insert(1LL << i));
        assert(xb.size() == 63);
        assert(!xb.insert(rng() >> 1));
        assert(xb.max() == std::numeric_limits<long long>::max());
        assert(xb.min(12345) == 0);
        assert(xb.kth_smallest(std::numeric_limits<long long>::max()) == std::numeric_limits<long long>::max());
        assert(xb.kth_largest(0) == std::numeric_limits<long long>::max());
        assert(xb.kth_smallest(777, 1000) == 777);
    }
    {
        // unsigned 64-bit, top bit used
        xor_basis<unsigned long long> xb;
        for (int i = 0; i < 64; i++) assert(xb.insert((rng() & ((1ULL << i) - 1)) | (1ULL << i)));
        assert(xb.size() == 64);
        assert(xb.max() == ~0ULL && xb.min() == 0);
        assert(xb.kth_smallest(~0ULL) == ~0ULL);
        assert(xb.kth_largest(~0ULL) == 0);
    }
    {
        // many inserts
        xor_basis<long long> xb;
        int added = 0;
        for (int i = 0; i < 200000; i++) added += xb.insert(rng() % (1LL << 60));
        assert(added == 60 && xb.size() == 60);
    }
    {
        xor_basis<long long> xb;
        assert(xb.size() == 0 && xb.contains(0) && !xb.contains(1));
        assert(xb.max(5) == 5 && xb.min(5) == 5 && xb.kth_smallest(0, 5) == 5 && xb.kth_largest(0, 5) == 5);
    }
    std::cout << "Hello World" << std::endl;
}

#line 1 "test/unit/xor_basis.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#line 3 "math/xor_basis.hpp"
#include <bit>
#line 5 "math/xor_basis.hpp"
#include <concepts>
#include <functional>
#include <limits>
#include <type_traits>
#line 10 "math/xor_basis.hpp"
template <std::integral T = long long> struct xor_basis {
    xor_basis() = default;
    int size() const {
        return int(b.size());
    }
    bool insert(T x) {
        x = reduce(x);
        if (x == 0) return false;
        T p = T(1) << (std::bit_width(std::make_unsigned_t<T>(x)) - 1);
        for (T& v : b) {
            if (v & p) v ^= x;
        }
        b.insert(std::lower_bound(b.begin(), b.end(), x, std::greater<T>()), x);
        return true;
    }
    bool contains(T x) const {
        return reduce(x) == 0;
    }
    T max(T xor_val = 0) const {
        check(xor_val);
        for (T v : b) xor_val = std::max(xor_val, T(xor_val ^ v));
        return xor_val;
    }
    T min(T xor_val = 0) const {
        return reduce(xor_val);
    }
    T kth_smallest(T k, T xor_val = 0) const {
        int r = size();
        assert(0 <= k && (r >= std::numeric_limits<T>::digits || k < (T(1) << r)));
        T x = reduce(xor_val);
        for (int i = 0; i < r; i++) {
            if ((k >> (r - 1 - i)) & 1) x ^= b[i];
        }
        return x;
    }
    T kth_largest(T k, T xor_val = 0) const {
        int r = size();
        T all = r == 0 ? 0 : ((T(1) << (r - 1)) - 1) * 2 + 1;
        assert(0 <= k && k <= all);
        return kth_smallest(all - k, xor_val);
    }

  private:
    std::vector<T> b;
    static void check([[maybe_unused]] T x) {
        if constexpr (std::is_signed_v<T>) assert(x >= 0);
    }
    T reduce(T x) const {
        check(x);
        for (T v : b) x = std::min(x, T(x ^ v));
        return x;
    }
};
#line 10 "test/unit/xor_basis.test.cpp"
int main() {
    std::mt19937_64 rng(20261027);
    for (int iter = 0; iter < 2000; iter++) {
        int n = rng() % 11, bits = 1 + rng() % 10;
        std::set<long long> span{0};
        xor_basis<long long> xb;
        for (int i = 0; i < n; i++) {
            long long x = rng() % (1LL << bits);
            bool in = span.count(x);
            assert(xb.contains(x) == in);
            assert(xb.insert(x) == !in);
            if (!in) {
                std::set<long long> nxt = span;
                for (long long v : span) nxt.insert(v ^ x);
                span = nxt;
            }
        }
        assert((1LL << xb.size()) == (long long)span.size());
        for (long long x = 0; x < (1LL << bits); x++) assert(xb.contains(x) == span.count(x));
        for (int t = 0; t < 5; t++) {
            long long xv = rng() % (1LL << bits);
            std::vector<long long> sorted;
            for (long long v : span) sorted.push_back(v ^ xv);
            std::sort(sorted.begin(), sorted.end());
            assert(xb.min(xv) == sorted.front());
            assert(xb.max(xv) == sorted.back());
            for (int k = 0; k < (int)sorted.size(); k++) {
                assert(xb.kth_smallest(k, xv) == sorted[k]);
                assert(xb.kth_largest(k, xv) == sorted[sorted.size() - 1 - k]);
            }
        }
    }
    {
        // full rank over 63 bits, signed long long
        xor_basis<long long> xb;
        for (int i = 0; i < 63; i++) assert(xb.insert(1LL << i));
        assert(xb.size() == 63);
        assert(!xb.insert(rng() >> 1));
        assert(xb.max() == std::numeric_limits<long long>::max());
        assert(xb.min(12345) == 0);
        assert(xb.kth_smallest(std::numeric_limits<long long>::max()) == std::numeric_limits<long long>::max());
        assert(xb.kth_largest(0) == std::numeric_limits<long long>::max());
        assert(xb.kth_smallest(777, 1000) == 777);
    }
    {
        // unsigned 64-bit, top bit used
        xor_basis<unsigned long long> xb;
        for (int i = 0; i < 64; i++) assert(xb.insert((rng() & ((1ULL << i) - 1)) | (1ULL << i)));
        assert(xb.size() == 64);
        assert(xb.max() == ~0ULL && xb.min() == 0);
        assert(xb.kth_smallest(~0ULL) == ~0ULL);
        assert(xb.kth_largest(~0ULL) == 0);
    }
    {
        // many inserts
        xor_basis<long long> xb;
        int added = 0;
        for (int i = 0; i < 200000; i++) added += xb.insert(rng() % (1LL << 60));
        assert(added == 60 && xb.size() == 60);
    }
    {
        xor_basis<long long> xb;
        assert(xb.size() == 0 && xb.contains(0) && !xb.contains(1));
        assert(xb.max(5) == 5 && xb.min(5) == 5 && xb.kth_smallest(0, 5) == 5 && xb.kth_largest(0, 5) == 5);
    }
    std::cout << "Hello World" << std::endl;
}

Back to top page