记录编号	424346	评测结果	AAAAAAAAAA
题目名称	[郑州培训2012] 数列的排序	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2017-07-13 11:17:43	内存使用	0.70 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN=10;

typedef long long LL;

LL k,fac[30];
bool v[30];
int n,b[30],a[101000];

LL cantor(int *a,int n) {
    LL tmp = 0;
    for (int i = 0; i < n; i++) {
      int k = 0;
      for (int j = i+1; j < n; j++) if(a[j] < a[i]) k++;
      tmp += fac[n-i-1]*k;
    }
    return tmp+1;
}

void Inv_cantor(int n,LL m) {
    --m;
    for (int i = 0; i < n; i++) v[i] = 0;
    for (int i = n-1; ~i; i--) {
      int k = m/fac[i],j; m %= fac[i];
      for (j = 0; j < n && k; j++) if(!v[j]) k--;
      while(v[j]) j++;
      v[b[n-i-1] = j] = true;
    }
    for (int i = 0; i < n; i++) ++b[i];
}

int c[30];
void Get() {
    for (int i = 0; i < 20; i++) c[i] = a[n-20+i];
    sort(c,c+20);
    for (int i = 0; i < 20; i++) b[i] = lower_bound(c,c+20,a[n-20+i])-c+1;
}

void Re_Get() {
    for (int i = 0; i < 20; i++) a[n-20+i] = c[b[i]-1];
}

inline LL Mod(LL x,LL p) {return x%p ? x%p : p;}

int main(int argc, char const *argv[]) {
    freopen("sortb.in","r",stdin); freopen("sortb.out","w",stdout);
    scanf("%d%lld",&n,&k);
    for (int i = 0; i < n; i++) scanf("%d",a+i);
    fac[0] = 1;
    for (int i = 1; i <= 20; i++) fac[i] = fac[i-1]*i;
    if(n <= 20) {
      Inv_cantor(n,Mod(cantor(a,n)+k,fac[n]));
      for (int i = 0; i < n; i++) printf("%d ",b[i]);
    } else {
      Get();
      LL nt = cantor(b,20);
      while(nt+k > fac[20]) {
         for (int i = 0; i < 20; i++) a[n-20+i] = c[19-i];
         next_permutation(a,a+n);
         k -= fac[20]-nt+1;
         nt = 1; Get();
      }
      Inv_cantor(20,nt+k);
      Re_Get();
      for (int i = 0; i < n; i++) printf("%d ",a[i]);
    }
    return 0;
}