Cod sursa(job #125193)

Utilizator znakeuJurba Andrei znakeu Data 20 ianuarie 2008 11:59:19
Problema Partitie Scor 60
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 9-a Marime 1.37 kb
#include <stdio.h>
#include <stdlib.h>

struct nr
{
	int v,p;	
};

int n,d,k;
nr v[300005];
int sm[300005];
int p[300005];
int e[300005];

int comp(const void *a, const void *b)
{
	nr *aa=(nr*) a, *bb=(nr*) b;
	nr x=*aa, y=*bb;
	return x.v-y.v;
}

int main()
{
	int i,j,t;
	
	FILE *in  = fopen("partitie.in","r");
	FILE *out = fopen("partitie.out","w");
	
	fscanf(in,"%d%d",&n,&d);
	for (i=0; i<n; i++)
	{
		fscanf(in,"%d",&v[i].v);
		v[i].p=i;		
	}
	
	qsort(v,n,sizeof(v[0]),comp);
	
	k=1;
	p[0]=v[0].v;
	sm[v[0].p]=1;
	e[0]=1;
	for (i=1; i<n; i++)
	{
		t=0;
		for (j=0; j<k && t==0; j++)
		{
			if(p[j]+d<=v[i].v)
			{
				p[j]=v[i].v;
				sm[v[i].p]=j+1;
				e[j]++;
				t=1;				
			}			
		}
		if (t==0)
		{
			p[k]=v[i].v;
			sm[v[i].p]=k+1;
			e[k]++;
			k++;
		}
	}
	for (i=0; i<n; i++)
	{
		if (e[sm[v[i].p]-1]==1)
		{
			for (j=0; j<n; j++)
				if (j<i)
				{
					if (e[sm[v[j].p]-1]>2)
						if (v[j].v+d<=v[i].v)
						{
							sm[v[j].p]=sm[v[i].p];
							e[sm[v[i].p]-1]++;
							j=n;
						}
				}
				else
					if (j>i)
					if (e[sm[v[j].p]-1]>2)
						if (v[j].v-d<=v[i].v)
						{
							sm[v[j].p]=sm[v[i].p];
							e[sm[v[i].p]-1]++;
							j=n;
						}			
		}
	}
	fprintf(out,"%d\n",k);
	for (i=0; i<n; i++)
		fprintf(out,"%d\n",sm[i]);
	fclose(in);
	fclose(out);
	
	return 0;
}