记录编号	424305	评测结果	AAAWWWWWWW
题目名称	1119.[郑州培训2012] 数列的排序	最终得分	30
用户昵称	rewine	是否通过	未通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-07-13 09:41:19	内存使用	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];

int cantor(int *a,int n) {
    int 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();
      Inv_cantor(20,Mod(cantor(b,20)+k,fac[20]));
      Re_Get();
      for (int i = 0; i < n; i++) printf("%d ",a[i]);
    }
    return 0;
}
/*
21 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/