Cod sursa(job #583742)

Utilizator maritimCristian Lambru maritim Data 22 aprilie 2011 12:51:00
Problema Restante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>

char A[36001][21];
int N;
int nr = 0;

int poz(int i,int li, int ls)
{
	char a = A[i][(li+ls)/2];
	A[i][(li+ls)/2] = A[i][0];
	A[i][0] = a;
	int i1 = 0;
	int j1 = -1;
	int c;
	while(li<ls)
	{
		if(A[i][li] > A[i][ls])
		{
			a = A[i][li];
			A[i][li] = A[i][ls];
			A[i][ls] = a;
			c = -i1;
			i1 = -j1;
			j1 = c;
		}
		li += i1;
		ls += j1;
	}
	return li;
}

void quicksort(int i,int li,int ls)
{
	if(li<ls)
	{
		int k = poz(i,li,ls);
		quicksort(i,li,k-1);
		quicksort(i,k+1,ls);
	}
}

void citire(void)
{
	FILE *f = fopen("restante.in","r");
	
	fscanf(f,"%d ",&N);
//	fgetc(f);
	for(int i=1;i<=N;i++)
	{
		fgets(A[i],200,f);
		quicksort(i,0,strlen(A[i])-2);
	}
	
	fclose(f);
}

int poz(int li, int ls)
{
	char a[16];
	strcpy(a,A[(li+ls)/2]);
	strcpy(A[(li+ls)/2],A[1]);
	strcpy(A[1],a);
	int i1 = 0;
	int j1 = -1;
	int c;
	while(li<ls)
	{
		if(strcmp(A[li],A[ls])>0 || strlen(A[li])>strlen(A[ls]))
		{
			strcpy(a,A[li]);
			strcpy(A[li],A[ls]);
			strcpy(A[ls],a);
			c = -i1;
			i1 = -j1;
			j1 = c;
		}
		li += i1;
		ls += j1;
	}
	return li;
}

void quicksort1(int li,int ls)
{
	if(li<ls)
	{
		int k = poz(li,ls);
		quicksort1(li,k-1);
		quicksort1(k+1,ls);
	}
}

void solve(void)
{
	quicksort1(1,N);
	int i = 1;
	while(i<=N)
	{
		int j = i+1;
		while(j<=N && !strcmp(A[i],A[j]))
			j ++;
		if(j == i+1)
			nr ++;
		i = j;
	}
}

int main()
{	
	FILE *f = fopen("restante.out","w");
	
	citire();
	solve();
	fprintf(f,"%d\n",nr);
	
	fclose(f);
	return 0;
}