proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/permutation.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/permutation.hpp"
#include "tools/pow.hpp"

using ll = long long;

struct group {
  using T = tools::permutation<ll>;
  inline static ll N;
  static T op(const T& lhs, const T& rhs) {
    return lhs * rhs;
  }
  static T e() {
    return T(N);
  }
  static T inv(const T& p) {
    return p.inv();
  }
};

// Source: https://atcoder.jp/contests/abc013/tasks/abc013_4
void abc013d(const ll& N, const ll& D, const std::vector<ll>& A, const std::vector<ll>& expected) {
  group::N = N;
  tools::permutation<ll> unit(N);
  for (ll i = 0; i < std::ssize(A); ++i) {
    unit.swap_from_right(A[i] - 1, A[i]);
  }

  const auto p = tools::pow<group>(unit, D);
  std::vector<ll> actual(p.begin(), p.end());
  for (auto& x : actual) ++x;

  assert_that(actual == expected);
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  abc013d(5, 1, std::vector<ll>({1, 4, 3, 4, 2, 3, 1}), std::vector<ll>({4, 2, 5, 3, 1}));
  abc013d(5, 2, std::vector<ll>({1, 4, 3, 4, 2, 3, 1}), std::vector<ll>({3, 2, 1, 5, 4}));
  abc013d(10, 300, std::vector<ll>({9, 1, 2, 5, 8, 1, 9, 3, 5, 6, 4, 5, 4, 6, 8, 3, 2, 7, 9, 6}), std::vector<ll>({3, 7, 2, 4, 5, 9, 6, 1, 8, 10}));

  for (ll n = 0; n <= 5; ++n) {
    std::vector<ll> expected(n);
    std::iota(expected.begin(), expected.end(), 0);
    ll id = 0;
    do {
      const auto actual = tools::permutation<ll>::from(n, id);
      assert_that(actual == tools::permutation<ll>(expected));
      assert_that(actual.id() == id);
      ++id;
    } while (std::next_permutation(expected.begin(), expected.end()));
  }

  return 0;
}

#line 1 "tests/permutation.test.cpp"
// competitive-verifier: STANDALONE

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/permutation.hpp"



#line 5 "tools/permutation.hpp"
#include <cassert>
#include <cstddef>
#line 10 "tools/permutation.hpp"
#include <ranges>
#include <utility>
#line 13 "tools/permutation.hpp"

namespace tools {
  template <typename T>
  class permutation {
    ::std::vector<int> m_perm;
    ::std::vector<int> m_inv;

    void verify_consistency() const {
#ifndef NDEBUG
      ::std::vector<bool> unique(this->size(), true);
      for (const auto x : this->m_perm) {
        assert(0 <= x && x < this->size());
        assert(unique[x]);
        unique[x] = false;
      }
#endif
    }

    void make_inv() {
      this->m_inv.resize(this->size());
      for (int i = 0; i < this->size(); ++i) {
        this->m_inv[this->m_perm[i]] = i;
      }
    }

  public:
    class iterator {
      ::std::vector<int>::const_iterator m_it;

    public:
      using reference = T;
      using value_type = T;
      using difference_type = ::std::ptrdiff_t;
      using pointer = const value_type*;
      using iterator_category = ::std::random_access_iterator_tag;

      iterator() = default;
      iterator(const ::std::vector<int>::const_iterator it) : m_it(it) {
      }

      reference operator*() const {
        return *this->m_it;
      }

      iterator& operator++() {
        ++this->m_it;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_it;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_it += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_it -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_it + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_it - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        return lhs.m_it - rhs.m_it;
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend bool operator==(const iterator lhs, const iterator rhs) {
        return lhs.m_it == rhs.m_it;
      }
      friend bool operator!=(const iterator lhs, const iterator rhs) {
        return lhs.m_it != rhs.m_it;
      }
      friend bool operator<(const iterator lhs, const iterator rhs) {
        return lhs.m_it < rhs.m_it;
      }
      friend bool operator<=(const iterator lhs, const iterator rhs) {
        return lhs.m_it <= rhs.m_it;
      }
      friend bool operator>(const iterator lhs, const iterator rhs) {
        return lhs.m_it > rhs.m_it;
      }
      friend bool operator>=(const iterator lhs, const iterator rhs) {
        return lhs.m_it >= rhs.m_it;
      }
    };

    permutation() = default;
    explicit permutation(const int n) : m_perm(n), m_inv(n) {
      ::std::iota(this->m_perm.begin(), this->m_perm.end(), 0);
      ::std::iota(this->m_inv.begin(), this->m_inv.end(), 0);
    }
    template <::std::ranges::range R>
    permutation(R&& r) : m_perm(::std::ranges::begin(r), ::std::ranges::end(r)) {
      this->verify_consistency();
      this->make_inv();
    }

    int size() const {
      return this->m_perm.size();
    }
    T operator[](const int i) const {
      assert(0 <= i && i < this->size());
      return this->m_perm[i];
    }
    iterator begin() const {
      return this->m_perm.begin();
    }
    iterator end() const {
      return this->m_perm.end();
    }

    ::tools::permutation<T>& swap_from_left(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      this->m_inv[this->m_perm[y]] = x;
      this->m_inv[this->m_perm[x]] = y;
      ::std::swap(this->m_perm[x], this->m_perm[y]);
      return *this;
    }
    ::tools::permutation<T>& swap_from_right(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      this->m_perm[this->m_inv[y]] = x;
      this->m_perm[this->m_inv[x]] = y;
      ::std::swap(this->m_inv[x], this->m_inv[y]);
      return *this;
    }

    long long id() const {
      if (this->size() == 0) return 0;

      ::std::vector<int> left(this->size());
      ::std::iota(left.begin(), left.end(), 0);

      ::std::vector<long long> fact(this->size());
      fact[0] = 1;
      for (int i = 1; i < this->size(); ++i) {
        fact[i] = fact[i - 1] * i;
      }

      long long id = 0;
      for (int i = 0; i < this->size(); ++i) {
        auto it = ::std::lower_bound(left.begin(), left.end(), this->m_perm[i]);
        id += ::std::distance(left.begin(), it) * fact[this->size() - 1 - i];
        left.erase(it);
      }

      return id;
    }

    static ::tools::permutation<T> from(const int n, long long id) {
      if (n == 0) return ::tools::permutation<T>(0);

      ::std::vector<int> left(n);
      ::std::iota(left.begin(), left.end(), 0);

      ::std::vector<long long> fact(n);
      fact[0] = 1;
      for (int i = 1; i < n; ++i) {
        fact[i] = fact[i - 1] * i;
      }

      ::std::vector<int> p;
      for (int i = 0; i < n; ++i) {
        const auto it = ::std::next(left.begin(), id / fact[n - i - 1]);
        p.push_back(*it);
        left.erase(it);
        id %= fact[n - i - 1];
      }

      return ::tools::permutation<T>(p);
    }

    ::tools::permutation<T> inv() const {
      return ::tools::permutation<T>(this->m_inv);
    }
    ::tools::permutation<T>& inv_inplace() {
      this->m_perm.swap(this->m_inv);
      return *this;
    }
    T inv(const int i) const {
      assert(0 <= i && i < this->size());
      return this->m_inv[i];
    }

    ::tools::permutation<T>& operator*=(const ::tools::permutation<T>& other) {
      assert(this->size() == other.size());
      for (int i = 0; i < this->size(); ++i) {
        this->m_inv[i] = other.m_perm[this->m_perm[i]];
      }
      this->m_perm.swap(this->m_inv);
      this->make_inv();
      return *this;
    }
    friend ::tools::permutation<T> operator*(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return ::tools::permutation<T>(lhs) *= rhs;
    }

    friend bool operator==(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return lhs.m_perm == rhs.m_perm;
    }
    friend bool operator!=(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return lhs.m_perm != rhs.m_perm;
    }

    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::permutation<T>& self) {
      os << '(';
      auto it = self.begin();
      const auto end = self.end();
      if (it != end) {
        os << *it;
        for (++it; it != end; ++it) {
          os << ", " << *it;
        }
      }
      return os << ')';
    }
    friend ::std::istream& operator>>(::std::istream& is, ::tools::permutation<T>& self) {
      for (auto& value : self.m_perm) {
        is >> value;
      }
      self.verify_consistency();
      self.make_inv();
      return is;
    }
  };
}


#line 1 "tools/pow.hpp"



#include <type_traits>
#line 6 "tools/pow.hpp"
#include <cmath>
#line 1 "tools/monoid.hpp"



#line 6 "tools/monoid.hpp"
#include <limits>
#line 1 "tools/gcd.hpp"



#line 6 "tools/gcd.hpp"

namespace tools {
  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 9 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 1 "tools/square.hpp"



#line 1 "tools/is_monoid.hpp"



#line 6 "tools/is_monoid.hpp"

namespace tools {

  template <typename M, typename = void>
  struct is_monoid : ::std::false_type {};

  template <typename M>
  struct is_monoid<M, ::std::enable_if_t<
    ::std::is_same_v<typename M::T, decltype(M::op(::std::declval<typename M::T>(), ::std::declval<typename M::T>()))> &&
    ::std::is_same_v<typename M::T, decltype(M::e())>
  , void>> : ::std::true_type {};

  template <typename M>
  inline constexpr bool is_monoid_v = ::tools::is_monoid<M>::value;
}


#line 6 "tools/square.hpp"

namespace tools {

  template <typename M>
  ::std::enable_if_t<::tools::is_monoid_v<M>, typename M::T> square(const typename M::T& x) {
    return M::op(x, x);
  }

  template <typename T>
  ::std::enable_if_t<!::tools::is_monoid_v<T>, T> square(const T& x) {
    return x * x;
  }
}


#line 9 "tools/pow.hpp"

namespace tools {

  template <typename M, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, typename M::T> pow(const typename M::T& base, const E exponent) {
    assert(exponent >= 0);
    return exponent == 0
      ? M::e()
      : exponent % 2 == 0
        ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2))
        : M::op(::tools::pow<M>(base, exponent - 1), base);
  }

  template <typename T, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, T> pow(const T& base, const E exponent) {
    assert(exponent >= 0);
    return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent);
  }

  template <typename T, typename E>
  auto pow(const T base, const E exponent) -> ::std::enable_if_t<!::std::is_integral_v<E>, decltype(::std::pow(base, exponent))> {
    return ::std::pow(base, exponent);
  }
}


#line 11 "tests/permutation.test.cpp"

using ll = long long;

struct group {
  using T = tools::permutation<ll>;
  inline static ll N;
  static T op(const T& lhs, const T& rhs) {
    return lhs * rhs;
  }
  static T e() {
    return T(N);
  }
  static T inv(const T& p) {
    return p.inv();
  }
};

// Source: https://atcoder.jp/contests/abc013/tasks/abc013_4
void abc013d(const ll& N, const ll& D, const std::vector<ll>& A, const std::vector<ll>& expected) {
  group::N = N;
  tools::permutation<ll> unit(N);
  for (ll i = 0; i < std::ssize(A); ++i) {
    unit.swap_from_right(A[i] - 1, A[i]);
  }

  const auto p = tools::pow<group>(unit, D);
  std::vector<ll> actual(p.begin(), p.end());
  for (auto& x : actual) ++x;

  assert_that(actual == expected);
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  abc013d(5, 1, std::vector<ll>({1, 4, 3, 4, 2, 3, 1}), std::vector<ll>({4, 2, 5, 3, 1}));
  abc013d(5, 2, std::vector<ll>({1, 4, 3, 4, 2, 3, 1}), std::vector<ll>({3, 2, 1, 5, 4}));
  abc013d(10, 300, std::vector<ll>({9, 1, 2, 5, 8, 1, 9, 3, 5, 6, 4, 5, 4, 6, 8, 3, 2, 7, 9, 6}), std::vector<ll>({3, 7, 2, 4, 5, 9, 6, 1, 8, 10}));

  for (ll n = 0; n <= 5; ++n) {
    std::vector<ll> expected(n);
    std::iota(expected.begin(), expected.end(), 0);
    ll id = 0;
    do {
      const auto actual = tools::permutation<ll>::from(n, id);
      assert_that(actual == tools::permutation<ll>(expected));
      assert_that(actual.id() == id);
      ++id;
    } while (std::next_permutation(expected.begin(), expected.end()));
  }

  return 0;
}
Back to top page