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

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

Depends on

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/abc264/tasks/abc264_d"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  string s;
  cin >> s;
  vector<int> a(7);
  const string at = "atcoder";
  rep(i, 7) rep(j, 7) if (at[i] == s[j]) a[i] = j;
  cout << asalib::math::inversion<int>(a) << endl;
  return 0;
}

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

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  string s;
  cin >> s;
  vector<int> a(7);
  const string at = "atcoder";
  rep(i, 7) rep(j, 7) if (at[i] == s[j]) a[i] = j;
  cout << asalib::math::inversion<int>(a) << endl;
  return 0;
}