Cod sursa(job #1425477)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 27 aprilie 2015 15:57:32
Problema Schi Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
#define N 30000
int val[N+1],v[N+1],poz[N],n;
void update(int poz,int val){
    while(poz<=n){
        v[poz]+=val;
        poz+=(poz&-poz);
    }
}
int sum(int poz){
    int s=0;
    while(poz){
        s+=v[poz];
        poz&=poz-1;
    }
int main(){
    FILE *fin,*fout;
    fin=fopen("schi.in","r");
    fout=fopen("schi.out","w");
    fscanf(fin,"%d",&n);
    int i;
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&val[i]);
        update(i,1);
    }
    for(i=n;i>=1;i--){
        int st=1,dr=n;
        while(st<=dr){
            int mij=(st+dr)/2;
            if(sum(mij)>=val[i])
                dr=mij-1;
            else
                st=mij+1;
        }
        update(st,-1);
        poz[st]=i;
    }
    for(i=1;i<=n;i++)
        fprintf(fout,"%d\n",poz[i]);
    return 0;
}