Cod sursa(job #1778665)

Utilizator andra1782Andra Alazaroaie andra1782 Data 13 octombrie 2016 23:02:29
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#define MAX 30001
int aib[MAX],v[MAX],c[MAX],n;

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

int query(int p){
    int s=0;

    while(p!=0){
        s+=aib[p];
        p-=p&(-p);
    }
    return s;
}

int cautare_binara(int e){
    int pas,i;

    pas=1<<15;
    i=0;
    while(pas!=0){
        if(i+pas<=n && query(i+pas)<=e)
            i+=pas;
        pas/=2;
    }
    return i;
}

int main(){
    FILE *fin=fopen("schi.in","r");
    FILE *fout=fopen("schi.out","w");
    int i,p;

    fscanf(fin,"%d",&n);
    for(i=1; i<=n; i++){
        fscanf(fin,"%d",&v[i]);
        aib[i]=i&(-i);
    }
    for(i=n; i>0; i--){
        p=cautare_binara(v[i]);
        c[p]=i;
        update(p+1,-1);
    }
    for(i=1; i<=n; i++)
        fprintf(fout,"%d\n",c[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}