[UVA][BIT] 11525 - Permutation
Problem F
Permutation
Input: Standard Input
Output: Standard Output
Given N and K find the N’th permutation of the integers from 1 to K when those permutations are lexicographically ordered. N starts from 0. Since N is very large N will be represented by a sequence of K non-negative integers S1, S2 ,…, Sk. From this sequence of integers N can be calculated with the following expression.
Input
First line of the input contains T(≤10) the number of test cases. Each of these test cases consists of 2 lines. First line contains a integer K(1≤K≤50000). Next line contains K integers S1, S2 ,…, Sk.(0≤Si≤K-i).
Output
For each test case output contains N’th permutation of the integers from 1 to K. These K integers should be separated by a single space.
Sample Input Output for Sample Input
432 1 031 0 042 1 1 041 2 1 0
|
3 2 12 1 33 2 4 12 4 3 1
|
Problemsetter: Abdullah al Mahmud
Special Thanks: Manzurur Rahman Khan
假如要找出 3 2 1 的第幾順位,
3 前面有 1 2, 故 2*2!, 2 前面還有 1, 故 1*1!, 最後是 0
因此是 2*2! + 1*1! + 0*0! = 5
因此從 1 開始算 3, 3被選出來
... 算 2, 算 1 ...
#include <stdio.h>
int main() {
int t, k, i, j, s;
unsigned C[50001];
scanf("%d", &t);
while(t--) {
scanf("%d", &k);
for(i = 1; i <= k; i++)
C[i] = 0;
for(i = 1; i <= k; i++) {
j = i;
while(j <= k) {
C[j]++;
j += j&(-j);
}
}
int l, r, m, sum1, sum2;
for(i = 1; i <= k; i++) {
scanf("%d", &s);
s++;
l = 1, r = k;
if(i != 1)
putchar(' ');
while(l <= r) {
m = (l+r)>>1;
j = m, sum1 = 0;
while(j > 0) sum1 += C[j], j -= j&(-j);
if(sum1 == s) {
j = m-1, sum2 = 0;
while(j > 0) sum2 += C[j], j -= j&(-j);
if(sum1 == sum2+1)
break;
else
r = m-1;
} else if(sum1 > s)
r = m-1;
else
l = m+1;
}
printf("%d", m);
j = m;
while(j <= k) {
C[j]--;
j += j&(-j);
}
}
puts("");
}
return 0;
}