Cod sursa(job #416238)

Utilizator feelshiftFeelshift feelshift Data 12 martie 2010 13:24:57
Problema Ordine Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <cstring>
int l,i,k;
char string[1000001],tmp;

FILE * in = fopen("ordine.in","rt");
FILE * out = fopen("ordine.out","wt");

void quicksort(char array[],int left,int right);

int main()
{
	fscanf(in,"%s",string);
	//fprintf(out,"Sirul initial este:\n");
	//fprintf(out,"%s\n\n",string);
	//fclose(in);
	l = strlen(string);
	
	quicksort(string,0,l-1);
	
	for(i=1;i<l;i++)
		if(string[i] == string[i-1])
			for(k=i+1;k<l;k++)
				if(string[i] != string[k])
				{
					tmp = string[i];
					string[i] = string[k];
					string[k] = tmp;
					//fprintf(out,"Am schimbat elementul %c cu elementul %c:\n",string[i],string[k]);
					//fprintf(out,"%s\n\n",string);
					break;
				}
	
	for(i=l-2;i>1;i--)
		if(string[i] == string[i+1])
			for(k=i-1;k>=1;k--)
				if(string[i] != string[k])
				{
					tmp = string[i];
					string[i] = string[k];
					string[k] = tmp;
					//fprintf(out,"Am schimbat elementul %c cu elementul %c:\n",string[i],string[k]);
					//fprintf(out,"%s\n\n",string);
					break;
				}
	
	//fprintf(out,"Sirul final este:\n");
	fprintf(out,"%s",string);
	//fclose(out);
	
	return (0);
}

void quicksort(char array[],int left,int right)
{
	int i,k,v;
	char tmp;
	
	if(left < right)
	{
		i = left - 1;
		k = right;
		v = array[right];
		
		for(;;)
		{
			while(array[++i] < v);
			while(array[--k] > v);
			
			if(i >= k)
				break;
			
			tmp = array[i];
			array[i] = array[k];
			array[k] = tmp;
		}
		
		tmp = array[i];
		array[i] = array[right];
		array[right] = tmp;
		
		quicksort(array,left,i-1);
		quicksort(array,i+1,right);
	}
}