結果
問題 | No.1311 Reverse Permutation Index |
ユーザー |
![]() |
提出日時 | 2020-12-08 00:03:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,500 ms |
コード長 | 2,617 bytes |
コンパイル時間 | 2,339 ms |
コンパイル使用メモリ | 200,892 KB |
最終ジャッジ日時 | 2025-01-16 19:09:36 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 |
ソースコード
#include <bits/stdc++.h>#pragma region my_templatestruct 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;#endifusing namespace std;#define ALL(c) begin(c), end(c)#pragma endregiontemplate <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';}