tests/math/inversion/arc136-b.test.cpp

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

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/arc136/tasks/arc136_b"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  ll inv_a = asalib::math::inversion<ll>(a);
  ll inv_b = asalib::math::inversion<ll>(b);
  sort(a.begin(), a.end()), sort(b.begin(), b.end());
  set<int> sa(a.begin(), a.end()), sb(b.begin(), b.end());
  if (a != b) {
    cout << "No" << endl;
  }
  else if (sa.size() != n || sb.size() != n) {
    cout << "Yes" << endl;
  }
  else {
    cout << (inv_a % 2 == inv_b % 2 ? "Yes" : "No") << endl;
  }
  return 0;
}

#line 1 "tests/math/inversion/arc136-b.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/arc136-b.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/arc136/tasks/arc136_b"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  ll inv_a = asalib::math::inversion<ll>(a);
  ll inv_b = asalib::math::inversion<ll>(b);
  sort(a.begin(), a.end()), sort(b.begin(), b.end());
  set<int> sa(a.begin(), a.end()), sb(b.begin(), b.end());
  if (a != b) {
    cout << "No" << endl;
  }
  else if (sa.size() != n || sb.size() != n) {
    cout << "Yes" << endl;
  }
  else {
    cout << (inv_a % 2 == inv_b % 2 ? "Yes" : "No") << endl;
  }
  return 0;
}

Back to top page