Cod sursa(job #251612)

Utilizator albuaAlbu Alexandru albua Data 2 februarie 2009 23:17:00
Problema Partitie Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <algorithm>
#define DMax 300009
#define DDMax 100000

using namespace std;

typedef struct
					{
					  long index, grupa,valoare;
					}element;
					
element a[DMax];
long n,dif,i,j,grupe;
long maxgr[DMax];
int ok;


void citire();
bool dupavaloare(element a, element b)
{
  return a.valoare<b.valoare;
}

bool dupaindex(element a, element b)
{
  return a.index<b.index;
}


int main()
{
	freopen("partitie.in","r",stdin);
	freopen("partitie.out","w",stdout);
	citire();
	sort(a+1,a+n+1,dupavaloare);
	a[1].grupa=1;
	maxgr[1]=a[1].valoare;
	grupe=1;
	for(i=2;i<=n;i++)
		{
			ok=1;
		  for(j=1;j<=grupe && ok;j++)
				if((a[i].valoare-maxgr[j])>=dif)
					{
					  maxgr[j]=a[i].valoare;
						a[i].grupa=j;
						ok=0;
					}
			if(ok)
				{
				  grupe++;
					maxgr[grupe]=a[i].valoare;
					a[i].grupa=grupe;
				}
		}
	//sort(a+1,a+n+1,dupaindex);
	for(i=1;i<=n;i++)
		maxgr[a[i].index]=a[i].grupa;
	printf("%ld\n",grupe);
	for(i=1;i<=n;i++)
		printf("%ld\n",maxgr[i]);
  return 0;
}

void citire()
{
  scanf("%ld %ld\n",&n,&dif);
	for(int i=1;i<=n;i++)
		{
		  scanf("%ld\n",&a[i].valoare);
			a[i].index=i;
		}
}