Cod sursa(job #810241)

Utilizator StefanLacheStefan Lache StefanLache Data 9 noiembrie 2012 22:27:02
Problema Schi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main()
{
    FILE *f=fopen ("schi.in","rt");
    FILE *g=fopen("schi.out","wt");
    int N,*v,*sol,*evidence,*bucket,size,value,i,j,Sum=0,x;
    fscanf(f,"%i",&N);
    v=(int *)malloc((N)*sizeof(int));
    sol=(int *)malloc((N)*sizeof(int));
    evidence=(int *)malloc((N)*sizeof(int));
    size=sqrt(N);
    value=N/size;
    bucket=(int *)malloc((size+1)*sizeof(int));
    for(i=0;i<N;++i)
        evidence[i]=1;
    for(j=0;j<size;++j)
        bucket[j]=N/size;
    for(i=0;i<N;++i)
        fscanf(f,"%i",&v[i]);
    for(i=N-1;i>=0;--i)
    {
        Sum=0;
        j=0;
        while(Sum+bucket[j]<v[i])
            {
                Sum+=bucket[j];
                ++j;
            }
        x=j*value;
        while(Sum+evidence[x]<v[i])
        {
                Sum+=evidence[x];
                ++x;
        }
        evidence[x]=0;
        bucket[x/value]--;
        sol[x]=i+1;
    }
    for(i=0;i<N;++i)
        fprintf(g,"%i\n",sol[i]);
    return 0;
}