tests/math/inversion/abc332-d.test.cpp

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Problem: https://atcoder.jp/contests/abc332/tasks/abc332_d

Depends on

• library/_internal/math/inversion.hpp
• library/_internal/modint-base.hpp
• 内部型 (library/_internal/types.hpp)
• 転倒数 (library/math/inversion.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include "../../../cpp/library/math/inversion.hpp"
#define PROBLEM "https://atcoder.jp/contests/abc332/tasks/abc332_d"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  vector a(h, vector<int>(w)), b(h, vector<int>(w));
  rep(i, h) rep(j, w) cin >> a[i][j];
  rep(i, h) rep(j, w) cin >> b[i][j];
  vector<int> px(h), py(w);
  iota(px.begin(), px.end(), 0);
  iota(py.begin(), py.end(), 0);
  constexpr int INF = 1e9;
  int ans = INF;
  do {
    do {
      bool ok = true;
      rep(i, h) rep(j, w) if (a[i][j] != b[px[i]][py[j]]) ok = false;
      if (ok) {
        int h_inv = asalib::math::inversion<int>(px);
        int w_inv = asalib::math::inversion<int>(py);
        ans = min(ans, h_inv + w_inv);
      }
    } while (next_permutation(py.begin(), py.end()));
  } while (next_permutation(px.begin(), px.end()));
  if (ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

#line 1 "tests/math/inversion/abc332-d.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#line 2 "library/math/inversion.hpp"

#line 4 "library/math/inversion.hpp"
using namespace std;

#line 2 "library/_internal/math/inversion.hpp"

#line 4 "library/_internal/math/inversion.hpp"
using namespace std;

#line 2 "library/_internal/types.hpp"

#include <concepts>
#include <type_traits>
using namespace std;

#line 2 "library/_internal/modint-base.hpp"

#line 5 "library/_internal/modint-base.hpp"
using namespace std;

namespace asalib {
  namespace _internal {
    class modint_base {};

    template<typename T>
    concept is_modint = is_base_of_v<modint_base, T>;
  }  // namespace _internal
}  // namespace asalib
#line 8 "library/_internal/types.hpp"

namespace asalib {
  namespace _internal {
    // ---------- concept definition ---------- //
    template<class T>
    concept integral_like = integral<T> || is_modint<T>;

    template<class T>
    concept floating_like = floating_point<T>;

    template<class T>
    concept numeric_like = integral_like<T> || floating_like<T>;

    // ---------- function definition ---------- //
    template<class T>
    T plus(T a, T b) { return a + b; }

    template<class T>
    T minus(T a, T b) { return a - b; }

    // ---------- constant definition ---------- //
    template<class T>
    T zero() { return 0; }
  }  // namespace _internal
}  // namespace asalib
#line 7 "library/_internal/math/inversion.hpp"

namespace asalib {
  namespace _internal {
    namespace math {
      template<integral_like T, bool eq, typename U, random_access_iterator iter>
      T inversion(iter first, iter last) {
        const size_t n = distance(first, last);
        if (n <= 1) return 0;
        const size_t mid = n >> 1;
        auto left = inversion<T, eq, U>(first, first + mid);
        auto right = inversion<T, eq, U>(first + mid, last);
        T inv = left + right;
        iter l = first, r = first + mid, l_end = first + mid, r_end = last;
        vector<U> tmp;
        tmp.reserve(n);
        while (l < l_end && r < r_end) {
          if constexpr (eq) {
            if (*l < *r) tmp.push_back(*l++);
            else {
              tmp.push_back(*r++);
              inv += mid - (l - first);
            }
          }
          else {
            if (*l <= *r) tmp.push_back(*l++);
            else {
              tmp.push_back(*r++);
              inv += mid - (l - first);
            }
          }
        }
        while (l < l_end) tmp.push_back(*l++);
        while (r < r_end) tmp.push_back(*r++);
        copy(tmp.begin(), tmp.end(), first);
        return inv;
      }
    }  // namespace math
  }  // namespace _internal
}  // namespace asalib
#line 8 "library/math/inversion.hpp"

namespace asalib {
  namespace math {
    template<_internal::integral_like T, typename U>
    T inversion(const vector<U>& a, const bool eq = false) {
      vector<U> t(a.begin(), a.end());
      if (eq) return _internal::math::inversion<T, true, U>(t.begin(), t.end());
      return _internal::math::inversion<T, false, U>(t.begin(), t.end());
    }
  }  // namespace math
}  // namespace asalib
#line 8 "tests/math/inversion/abc332-d.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc332/tasks/abc332_d"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  vector a(h, vector<int>(w)), b(h, vector<int>(w));
  rep(i, h) rep(j, w) cin >> a[i][j];
  rep(i, h) rep(j, w) cin >> b[i][j];
  vector<int> px(h), py(w);
  iota(px.begin(), px.end(), 0);
  iota(py.begin(), py.end(), 0);
  constexpr int INF = 1e9;
  int ans = INF;
  do {
    do {
      bool ok = true;
      rep(i, h) rep(j, w) if (a[i][j] != b[px[i]][py[j]]) ok = false;
      if (ok) {
        int h_inv = asalib::math::inversion<int>(px);
        int w_inv = asalib::math::inversion<int>(py);
        ans = min(ans, h_inv + w_inv);
      }
    } while (next_permutation(py.begin(), py.end()));
  } while (next_permutation(px.begin(), px.end()));
  if (ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

Back to top page