Cod sursa(job #1765298)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 26 septembrie 2016 16:34:24
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#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;
}