Cod sursa(job #1475792)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 24 august 2015 12:41:20
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#define LS (nod<<1)
#define RS ((nod<<1)+1)
const char iname[] = "farfurii.in";
const char oname[] = "farfurii.out";
const int MAXN = 100005;

int n, tree[4*MAXN];
long long k;
long long getInversiuni(int i){
    return (1LL * (n-i)*(n-i-1))/2;
}
void update(int nod, int st, int dr, int poz, int val){
    if(st == dr) tree[nod] += val;
    else{
        int mij = (st + dr)>>1;
        if(poz <= mij) update(LS, st, mij, poz, val);
        else    update(RS, mij+1, dr, poz, val);
        tree[nod] = tree[RS] + tree[LS];
    }
}
int querry(int nod, int st, int dr, int poz){
    if(st == dr)return dr;
    int mij = (st + dr) >> 1;
    if(tree[LS] >= poz)
        return querry(LS, st, mij, poz);
    //arb[LS] < poz
    poz -= tree[LS];
    return querry(RS, mij+1, dr, poz);
}
int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    scanf("%d %lld", &n, &k);
    for(int i = 1; i <= n; ++i){
        update(1,1,n,i,1);
    }
    int st = 1;
    while(getInversiuni(st) >= k){
        int poz = querry(1,1,n,1);
        printf("%d ", poz);
        update(1,1,n,poz,-1);
        ++st;
    }
    for(int i = st; i <= n; ++i){
        int poz = k - getInversiuni(st);
        k = k-poz;
        poz = querry(1,1,n,poz+1);
        printf("%d ", poz);
        update(1,1,n,poz,-1);
        ++st;
    }
    return 0;
}