結果

問題 No.1311 Reverse Permutation Index
ユーザー pes_magicpes_magic
提出日時 2020-12-20 16:19:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 1,090 bytes
コンパイル時間 833 ms
コンパイル使用メモリ 77,356 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-21 11:53:04
合計ジャッジ時間 1,325 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;

long long getOrder(const vector<int>& v){
    const int N = v.size();
    vector<int> used(N+1, 0);
    long long res = 0;
    for(int i=0;i<N-1;i++){
        res *= N-i;
        int add = v[i]-1;
        for(int j=1;j<v[i];j++) add -= used[j];
        used[v[i]] = 1;
        res += add;
    }
    return res;
}

vector<int> getPerm(long long s, int N){
    vector<long long> fact(N);
    fact[0] = fact[1] = 1;
    for(int i=2;i<N;i++) fact[i] = i * fact[i-1];
    vector<int> used(N, 0);
    vector<int> res;
    for(int i=0;i<N;i++){
        int ord = s/fact[N-1-i];
        s %= fact[N-1-i];
        for(int j=0;j<N;j++){
            if(used[j]) continue;
            if(ord == 0){
                res.push_back(j+1);
                used[j] = 1;
                break;
            }
            --ord;
        }
    }
    return res;
}


int main(){
    int N;
    long long S;
    cin >> S >> N;
    auto v = getPerm(S, N);
    vector<int> r(N);
    for(int i=0;i<N;i++) r[v[i]-1] = i+1;
    cout << getOrder(r) << endl;
}
0