結果
問題 |
No.1311 Reverse Permutation Index
|
ユーザー |
|
提出日時 | 2020-12-20 16:19:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,500 ms |
コード長 | 1,090 bytes |
コンパイル時間 | 666 ms |
コンパイル使用メモリ | 75,632 KB |
最終ジャッジ日時 | 2025-01-17 04:52:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 |
ソースコード
#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; }