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