結果
問題 | No.1311 Reverse Permutation Index |
ユーザー | risujiroh |
提出日時 | 2020-12-08 00:03:09 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,500 ms |
コード長 | 2,617 bytes |
コンパイル時間 | 2,229 ms |
コンパイル使用メモリ | 208,900 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-17 16:45:54 |
合計ジャッジ時間 | 2,975 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
ソースコード
#include <bits/stdc++.h> #pragma region my_template struct Rep { struct I { int i; void operator++() { ++i; } int operator*() const { return i; } bool operator!=(I o) const { return i < *o; } }; const int l_, r_; Rep(int l, int r) : l_(l), r_(r) {} Rep(int n) : Rep(0, n) {} I begin() const { return {l_}; } I end() const { return {r_}; } }; struct Per { struct I { int i; void operator++() { --i; } int operator*() const { return i; } bool operator!=(I o) const { return i > *o; } }; const int l_, r_; Per(int l, int r) : l_(l), r_(r) {} Per(int n) : Per(0, n) {} I begin() const { return {r_ - 1}; } I end() const { return {l_ - 1}; } }; template <class F> struct Fix : private F { Fix(F f) : F(f) {} template <class... Args> decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; template <class T = int> T scan() { T res; std::cin >> res; return res; } template <class T, class U = T> bool chmin(T& a, U&& b) { return b < a ? a = std::forward<U>(b), true : false; } template <class T, class U = T> bool chmax(T& a, U&& b) { return a < b ? a = std::forward<U>(b), true : false; } #ifndef LOCAL #define DUMP(...) void(0) template <int OnlineJudge, int Local> constexpr int OjLocal = OnlineJudge; #endif using namespace std; #define ALL(c) begin(c), end(c) #pragma endregion template <class T = int> using V = vector<T>; int64_t perm2i(const V<>& p) { int n = p.size(); static V<int64_t> fact{1}; while (fact.size() < n) { fact.push_back(fact.size() * fact.back()); } int64_t res = 0; for (int i = 0; i < n; ++i) { int cnt = 0; for (int j = i + 1; j < n; ++j) { cnt += p[i] > p[j]; } res += cnt * fact[n - 1 - i]; } return res; } V<> i2perm(int n, int64_t x) { static V<int64_t> fact{1}; while (fact.size() < n) { fact.push_back(fact.size() * fact.back()); } V<> res(n); V<bool> used(n); for (int i = 0; i < n; ++i) { while (used[res[i]]) ++res[i]; for (int _ = 0; _ < x / fact[n - 1 - i]; ++_) { ++res[i]; while (used[res[i]]) ++res[i]; } used[res[i]] = true; x %= fact[n - 1 - i]; } return res; } int main() { cin.tie(nullptr)->sync_with_stdio(false); cout << fixed << setprecision(20); auto i = scan<int64_t>(); int n = scan(); auto p = i2perm(n, i); vector<int> ip(n); for (int i : Rep(n)) ip[p[i]] = i; cout << perm2i(ip) << '\n'; }