24h購物| | PChome| 登入
2012-05-19 19:05:39| 人氣530| 回應0 | 上一篇 | 下一篇

[UVA][zkw式ST] 11525 - Permutation

推薦 0 收藏 0 轉貼0 訂閱站台

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

4
3
2 1 0
3
1 0 0
4
2 1 1 0
4
1 2 1 0

 

3 2 1
2 1 3
3 2 4 1
2 4 3 1

 


Problemsetter: Abdullah al Mahmud

Special Thanks: Manzurur Rahman Khan

寫到我都以為我在寫二元搜尋樹了

#include <stdio.h>

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;
}

台長: Morris
人氣(530) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Tree] 11350 - Stern-Brocot Tree
此分類上一篇:[UVA][BIT] 11525 - Permutation

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文