Pagini recente » Cod sursa (job #2449609) | Cod sursa (job #3278232) | Cod sursa (job #845269) | Cod sursa (job #2477737) | Cod sursa (job #1765298)
#include <cstdio>
#include <algorithm>
using namespace std;
int aib[100005];
int ans[100005];
void update(int pos, int x, int n){
for(;pos <= n;pos += pos&(-pos)){
aib[pos] += x;
}
}
int binarySearch(long long lf, long long rg, long long x){
long long i,step;
for(step = 1;step <= rg;step <<= 1);
for(i = lf-1;step;step >>= 1){
if(i + step <= rg && aib[i + step] <= x){
i += step;
x -= aib[i];
}
}
return i;
}
int main()
{
freopen("farfurii.in", "r", stdin);
freopen("farfurii.out", "w", stdout);
long long n,k,i,j,pos;
scanf("%lld %lld", &n, &k);
for(i = 1;i <= n;i++){
update(i, 1, n);
}
for(i = n;i >= 2;i--){
if(k > (i-1)*(i-2)/2){
pos = binarySearch(1, n, k - (i-1)*(i-2)/2) + 1;
k -= k - (i-1)*(i-2)/2;
ans[i] = pos;
update(pos, -1, n);
}else{
pos = binarySearch(1, n, 0) + 1;
ans[i] = pos;
update(pos, -1, n);
}
}
ans[1] = binarySearch(1, n, 0)+1;
for(i = 1,j = n;i < j;i++, j--){
swap(ans[i], ans[j]);
}
for(i = 1;i <= n;i++){
printf("%d ",ans[i]);
}
return 0;
}