Cod sursa(job #2133798)

Utilizator mariastStoichitescu Maria mariast Data 17 februarie 2018 12:15:02
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
#define lsb(p) ((-p)&p)
using namespace std;
int arb[30010],a[30010],vec[30010],n;
void update(int v,int p){
    for(int i=p;i<=n;i+=lsb(i)){
        arb[i]+=v;
    }
}
int sum(int p){
    int suma=0;
    for(int i=p;i>0;i-=lsb(i)){
        suma+=arb[i];
    }
    return suma;
}
int cb(int x){
    int st=1,dr=n,m,val;
    while(st<=dr){
        m=(st+dr)/2;
        int aux=sum(m);
        if(aux==x){
            dr=m-1;
            val=m;
        }
        else if(aux<x){
            st=m+1;
        }
        else dr=m-1;
    }
    return val;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        update(1,i);
    }
    for(int i=n;i>=1;--i){
        int  aux=cb(a[i]);
        vec[aux]=i;
        update(-1,aux);
    }
    for(int i=1;i<=n;++i){
        printf("%d\n",vec[i]);
    }
}