test/yukicoder/1311/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/no/1311
• Link: View error logs on GitHub Actions

Depends on

• Permutation (Mylib/Math/permutation.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/1311"

#include <iostream>
#include "Mylib/Math/permutation.cpp"

namespace hl = haar_lib;

int main() {
  int64_t N, S;
  std::cin >> N >> S;
  int64_t ans = hl::permutation_to_index(hl::inverse_permutation(hl::index_to_permutation(N, S)));

  std::cout << ans << "\n";

  return 0;
}

#line 1 "test/yukicoder/1311/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1311"

#include <iostream>
#line 2 "Mylib/Math/permutation.cpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <vector>

namespace haar_lib {
  std::vector<int> index_to_permutation(int64_t N, int S) {
    std::vector<int> ret;

    __gnu_pbds::tree<
        int, __gnu_pbds::null_type, std::less<int>,
        __gnu_pbds::rb_tree_tag,
        __gnu_pbds::tree_order_statistics_node_update>
        set;

    std::vector<int64_t> p(S + 1, 1);
    for (int i = 0; i < S; ++i) {
      p[i + 1] = p[i] * (i + 1);
      set.insert(i);
    }

    for (int i = S; --i >= 0;) {
      int64_t index = N / p[i];

      int j = *set.find_by_order(index);
      ret.push_back(j);
      set.erase(j);

      N %= p[i];
    }

    return ret;
  }

  template <typename T = int64_t>
  T permutation_to_index(const std::vector<int> &a) {
    const int N = a.size();
    T ret       = 0;

    __gnu_pbds::tree<
        int, __gnu_pbds::null_type, std::less<int>,
        __gnu_pbds::rb_tree_tag,
        __gnu_pbds::tree_order_statistics_node_update>
        set;

    std::vector<T> p(N + 1, 1);
    for (int i = 0; i < N; ++i) {
      p[i + 1] = p[i] * (i + 1);
      set.insert(i);
    }

    for (int i = 0; i < N; ++i) {
      int k = set.order_of_key(a[i]);
      ret += p[N - 1 - i] * k;
      set.erase(a[i]);
    }

    return ret;
  }

  std::vector<int> inverse_permutation(const std::vector<int> &a) {
    const int N = a.size();
    std::vector<int> ret(N);
    for (int i = 0; i < N; ++i) {
      ret[a[i]] = i;
    }

    return ret;
  }
}  // namespace haar_lib
#line 5 "test/yukicoder/1311/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int64_t N, S;
  std::cin >> N >> S;
  int64_t ans = hl::permutation_to_index(hl::inverse_permutation(hl::index_to_permutation(N, S)));

  std::cout << ans << "\n";

  return 0;
}

Back to top page