[UVA][zkw式ST] 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
寫到我都以為我在寫二元搜尋樹了
int main() {
int t, k, s, i, j, M;
unsigned tree[150000];
scanf("%d", &t);
while(t--) {
scanf("%d", &k);
for(M = 1; M < k+1; M <<= 1);
for(i = 2*M-1; i > 0; i--) {
if(i >= M)
tree[i] = 1;
else
tree[i] = tree[i<<1]+tree[i<<1|1];
}
int idx;
for(i = 1; i <= k; i++) {
scanf("%d", &s);
s++;
for(idx = 1; idx < M;) {
if(tree[idx<<1] < s)
s -= tree[idx<<1], idx = idx<<1|1;
else
idx = idx<<1;
}
if(i != 1)
putchar(' ');
printf("%d", idx-M+1);
while(idx > 0)
tree[idx]--, idx >>= 1;
}
puts("");
}
return 0;
}