結果
問題 | No.1311 Reverse Permutation Index |
ユーザー |
![]() |
提出日時 | 2020-12-08 00:26:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,500 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 1,533 ms |
コンパイル使用メモリ | 170,908 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 00:19:21 |
合計ジャッジ時間 | 2,112 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;//template#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(v) (v).begin(),(v).end()typedef long long int ll;const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}//endtemplate<typename T>struct BIT{int n; T m=0; vector<T> val;BIT(int _n):n(_n),val(_n+10){}void clear(){val.assign(n+10,0); m=0;}void add(int i,T x){for(i++;i<=n;i+=(i&-i))val[i]+=x;m+=x;}T sum(int i){T res=0;for(i++;i;i-=(i&-i))res+=val[i];return res;}};int main(){ll id; int n;cin>>id>>n;ll fact[25];fact[0]=1;rep(i,0,20)fact[i+1]=fact[i]*(i+1);vector<int> a(n),used(n,0);rep(i,0,n){ll cnt=id/fact[n-i-1];id-=cnt*fact[n-i-1];int val=1;while(1){if(used[val]){val++; continue;}if(cnt==0)break;cnt--;val++;}a[i]=val; used[val]=1;}for(auto& x:a)cerr<<x<<' ';cerr<<'\n';vector<int> b(n);rep(i,0,n)b[a[i]-1]=i+1;a=b;ll res=0; BIT<int> bit(n+1);rep(i,0,n){res+=fact[n-i-1]*(a[i]-1-bit.sum(a[i]));bit.add(a[i],1);}cout<<res<<endl;return 0;}