Pagini recente » Cod sursa (job #2361000) | Cod sursa (job #954103) | Cod sursa (job #1085350) | Cod sursa (job #1976345) | Cod sursa (job #810233)
Cod sursa(job #810233)
#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;
}