Cod sursa(job #127968)

Utilizator floringh06Florin Ghesu floringh06 Data 25 ianuarie 2008 17:17:56
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define FIN "restante.in"
#define FOUT "restante.out"
#define MAX_N 36005
        
char A[MAX_N][20];
int n, i;

     void preproc ()
     {
          int i, j;
          int a[1 << 5];
          
          for (i = 1; i <= n; ++i)
          {
              int L = strlen (A[i]);
              
              memset (a, 0, sizeof (a));
              for (j = 0; j < L; ++j)
                  ++a[A[i][j] - 96];
              int k = 0;
              for (j = 1; j <= 26; ++j)
                  while (a[j]--)
                        A[i][k++] = j + 96;       
          }        
     }
     
     int cmp (int i, int j)
     {
         int l1 = strlen (A[i]) - 1;
         int l2 = strlen (A[j]) - 1;
         
         if (l2 < l1) return 1;
         if (l1 < l2) return 0;
         
         for (int k = 0; k <= l1; ++k)
             if (A[i][k] < A[j][k]) return 0;
                else if (A[i][k] > A[j][k]) return 1;
         return 1;
     }         
     
     int part (int st, int dr)
     {
         int i, j, s = 1;
         i = st;
         j = dr;
         while (i < j)
         {
               if (cmp (i, j))
               {
                       char x[20] = "";
                       memcpy (x, A[i], sizeof (x));
                       memcpy (A[i], A[j], sizeof (A[j]));
                       memcpy (A[j], x, sizeof (x));
                       s = 1 - s;
               }
               if (s) ++i; else --j;
         }
         return i;
     }               
     
     void sort (int st, int dr)
     {
          if (st < dr)
          {
                 int p = part (st, dr);
                 sort (st, p - 1);
                 sort (p + 1, dr);
          }
     }
     
     void solve ()
     {
          int i, j;
          int sol = 0;
          for (i = 1; i <= n; ++i)
              if (memcmp (A[i], A[i - 1], 19) && memcmp (A[i], A[i + 1], 19))
                 ++sol;
          printf ("%d\n", sol);
     }

     int main ()
     {
         freopen (FIN, "r", stdin);
         freopen (FOUT, "w", stdout);
         
         scanf ("%d\n", &n);
         for (i = 1; i <= n; ++i)
             gets (A[i]);
         
         preproc ();
         sort (1, n);
         solve ();
         
         return 0;
     }