Cod sursa(job #810233)

Utilizator StefanLacheStefan Lache StefanLache Data 9 noiembrie 2012 22:11:58
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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+1)*sizeof(int));
    sol=(int *)malloc((N+1)*sizeof(int));
    evidence=(int *)malloc((N+1)*sizeof(int));
    size=sqrt(N);
    value=N/size;
    bucket=(int *)malloc((size+1)*sizeof(int));
    for(i=1;i<=N;++i)
        evidence[i]=1;
    for(j=0;j<size;++j)
        bucket[j]=N/size;
    for(i=1;i<=N;++i)
        fscanf(f,"%i",&v[i]);
    for(i=N;i>=1;--i)
    {
        Sum=0;
        j=0;
        while(Sum<v[i])
        {
            if(Sum+bucket[j] < v[i])
                {
                    Sum+=bucket[j];
                    ++j;
                }
                else break;
        }
        x=j*value+1;
        while(Sum<v[i])
        {
            if(Sum+evidence[x] <= v[i])
            {
                Sum+=evidence[x];
                ++x;
            }
            else break;
        }
        --x;
        evidence[x]=0;
        bucket[x/value]--;
        sol[x]=i;
    }
    for(i=1;i<=N;++i)
        fprintf(g,"%i\n",sol[i]);
    return 0;
}