Cod sursa(job #1427624)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 mai 2015 17:58:13
Problema Schi Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>
#define zeros(x) (((x-1)^x)&x)
#define MAXN 30001
int aib[MAXN],n,v[MAXN],v1[MAXN];
inline void add(int x,int nr){
    int i;
    for(i=x;i<=n;i+=zeros(i))
        aib[i]+=nr;
}
inline int sum(int x){
    int s=0,i;
    for(i=x;i>0;i-=zeros(i))
        s+=aib[i];
    return s;
}
int main(){
    FILE*fi,*fout;
    int i,mij,st,dr;
    fi=fopen("schi.in" ,"r");
    fout=fopen("schi.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n;i++){
       fscanf(fi,"%d" ,&v[i]);
       add(i+1,1);
    }
    for(i=n-1;i>=0;i--){
        st=1;
        dr=n;
        while(st<=dr){
            mij=(st+dr)/2;
            if(sum(mij)>=v[i])
                dr=mij-1;
            else
                st=mij+1;
        }
        add(st,-1);
        v1[st]=i+1;
    }
    for(i=1;i<=n;i++)
        fprintf(fout,"%d " ,v1[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}