Rockethon 2015, problem: (B2) Permutations

排法必為a b c .... c-1.... b+1 b-1..... a+1 a-1...... 1

從ptr = 0構造，若當前選k, 則排名必從 sigma_(i<=k) 2^(剩下長度 - i) 增加
所以可以搜到當前要填哪個數字，假如選到 r
則建好
r 空 .... 空  r-1 ..... 1

然後再繼續往下建

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

int n;
int64 m;
int64 tab[60];
int main(){

    tab[0] = 1;
    tab[1] = 1;
    for(int lx = 2;lx < 60;lx++)
        tab[lx] = tab[lx-1]<<1;

    scanf("%d %I64d", &n, &m);
    
    int build[100];

    int left_ptr = 0;
    int right_ptr = n-1;
    int last_value = 0;
    while(left_ptr <= right_ptr){
        int64 sum = 0;
        int ly = 1;
        for(;ly <= n - last_value;ly++){
            sum += tab[n - last_value - ly];
            if(sum >= m){
                break;
            }
        }
        sum -= tab[n - last_value - ly];
        m -= sum;
        build[left_ptr++] = ly + last_value;
        for(int lx = 0;lx < ly-1;lx++)
            build[right_ptr--] = lx + 1 + last_value;
        last_value += ly;
    }
    for(int lx = 0;lx < n;lx++)
        printf("%d ", build[lx]);
    printf("\n");
    return 0;
}