Welcome, guest! Login / Register - Why register?
Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)

Paste

Pasted as C++ by andrew ( 7 years ago )
#include <iostream> 
#include <algorithm> 
#include <queue> 
#include <stack> 
#include <map>
#include <cmath> 
#include <vector> 
#include <set> 

#define INF (2147483647)

using namespace std;

int n, m, mn = 1;
vector<int> mass, tree;

int fact(int a){ 
    if (a == 0)
        return 1;
    return a*fact(a-1);
}

void add(int i, int val) {
    for(; i; i>>=1)
        tree[i] += val;
}

int main() {
    cin >> n >> m;
    n++; m--;
    
    while(mn < n) {
        mn *= 2;
    }
    
    mass.assign(n, 1);
    mass[0] = 0;
    tree.assign(4*n, 0);
    
    for(int i = 0; i < n; i++)
        tree[mn + i] = mass[i];    
    for(int i = mn - 1; i > 0; i--)
        tree[i] = tree[2*i] + tree[2*i+1];
        
    
    
    for(int i = 0; i < n; i++) {
        int k = m/fact(n - 1) + 1;
        int v = 1;
        while(2*v < tree.size()) {
            if(tree[2*v] >= k){
                v *= 2;            
            } else {
                k -= tree[2*v];
                v = 2*v+1;
            }    
        }
        cout << (v - mn) << " ";
        add(v, -1);
   }
    
    return 0;
}

 

Revise this Paste

Your Name: Code Language: