Cod sursa(job #207184)

Utilizator mordredSimionescu Andrei mordred Data 12 septembrie 2008 00:18:41
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#include <string.h>
#define nmax 36001
#define lmax 32
#define copy(a,b) for(ii=0;ii<16;++ii) a[ii] = b[ii];
#define swap(a,b) for(ii=0;ii<16;++ii) aux=a[ii],a[ii]=b[ii],b[ii]=aux;

int n;
char x[nmax][lmax];
int i, m, aux, ii, ix;

int cmp(char a[lmax], char b[lmax]){
 for(int i=0;i<16;++i) if(a[i]!=b[i])   return (a[i]>b[i])?-1:1;
 return 0;
}

void smallquicksort(int start, int end){
 if(end-start<1) return;
 int pivot = x[ix][start], i = start, k = end;
 while(k>i)
     {
     while(x[ix][i]<=pivot && i<=end && k > i)
         ++i;
     while(x[ix][k]>pivot && k>=start && k>=i)
         --k;
     if(k>i){
         aux = x[ix][i];
         x[ix][i] = x[ix][k];
         x[ix][k] = aux;
         }
     }
 aux = x[ix][start];
 x[ix][start] = x[ix][k];
 x[ix][k] = aux;
 smallquicksort(start,k-1);
 smallquicksort(k+1,end);
}

void quicksort(int start, int end){
 if(end-start<1) return;
 char pivot[lmax];
 int i = start, k = end;
 copy(pivot, x[start]);
 while(k>i)
    {
    while(cmp(x[i],pivot) > -1 && i <= end   && k >  i)
        ++i;
    while(cmp(x[k],pivot) <  0 && k >= start && k >= i)
        --k;
    if(k>i){
        swap(x[i],x[k]);
        }
    }
 swap(x[start],x[k]);
 quicksort(start,k-1);
 quicksort(k+1,end);
}

int main(){
 freopen("restante.in","r",stdin);
 freopen("restante.out","w",stdout);
 
 scanf("%d",&n);
 
 fgets(x[0],100,stdin);
 
 for(i=0;i<n;++i)
    fgets(x[i],100,stdin),
    x[i][strlen(x[i])-1]=0,
    ix = i,
    smallquicksort(0,strlen(x[i])-1);
 
 quicksort(0,n-1);
 
 m = !cmp(x[0],x[1])?0:1;
 
 for(i=1;i<n;++i)
    if(cmp(x[i],x[i+1])&&cmp(x[i],x[i-1]))
        ++m;
        
 printf("%d\n",m);
 return 0;
}