Cod sursa(job #1774852)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 9 octombrie 2016 15:26:04
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>

#define NMAX 30001
#define INFINIT 999999

using namespace std;

int n;

int aib[NMAX],v[NMAX],clasament[NMAX];

void update (int p,int val) {
    for (; p<=n; p+=p&(-p))
        aib[p] += val;
}

int querry (int p) {
    int s = 0;
    for (; p>0; p-=p&(-p))
        s += aib[p];
    return s;
}

int binary_search(int val) {
    int b = 1,e = n,l = INFINIT,mid,poz;
    while (b <= e) {
        mid = (b + e) / 2;
        poz = querry(mid);
        if (poz == val && l > mid)
            l = mid;
        else if (poz < val)
            b = mid + 1;
        else
            e = mid - 1;
    }
    return l;
}

int main() {
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i,poz;
    scanf("%d",&n);
    for (i=1; i<=n; i++) {
        scanf("%d",&v[i]);
        aib[i] = i & (-i);
    }
    for (i=n; i>0; i--) {
        poz = binary_search(v[i]);
        clasament[poz] = i;
        update(poz,-1);
    }
    for (i=1; i<=n; i++)
        printf("%d\n",clasament[i]);
    return 0;
}