Cod sursa(job #657435)

Utilizator idomiralinIdomir Alin idomiralin Data 6 ianuarie 2012 16:45:58
Problema Restante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
# include <cstdio>
# include <cstring>
# include <algorithm>

using namespace std;

int poz[36005], poz1[36005],viz[36005];
char b[500000];
void sort(int st,int dr)
{int i,j,piv,aux;   
    i=st;j=dr;piv=b[(st+dr)/2];
    while(i<=j)
    {
              while (b[i]<piv) ++i;
              while (b[j]>piv) --j;
              
              if (i<=j)
              {
                    aux=b[i];
                    b[i]=b[j];
                    b[j]=aux;   
                    aux=poz[i];
                    poz[i]=poz[j];
                    poz[j]=aux;
                    ++i;--j;}
               }
    
    if (st<j) sort(st,j);
    if (i<dr) sort(i,dr);
}

int n, i, j, lim, lim1, ct, ct1, ok, contor, pozi, pozj;    
char s[500000], a[500000];
int main()
{
    freopen("restante.in","r",stdin);
    freopen("restante.out","w",stdout);
    
    scanf("%d",&n);
    
    fread(s,1,1000,stdin); 
    lim1 = 1;
    for (i = 1; i <= strlen(s); i++)
       if (s[i] == '\n')
       {
                      lim = i - 1;
                      sort(s + lim1, s + lim + 1); //sortez literele din fiecare cuvant
                      b[++ct] = s[lim1]; // retin la fiecare prima litera
                      poz[ct] = lim1; // pozitia de inceput care se schimba dupa ce sortez
                      poz1[ct] = lim1; // poz de inc care nu se schimba
                      lim1 = lim + 2;
                      
            }
    
    sort(1, n); // sortez cuvintele dupa prima litera
   
    for (i = 1; i <= ct; i++)
    {
        for (j = poz[i]; s[j] != '\n'; j++) 
           a[++ct1] = s[j];
            //printf("%c",a[ct1]);}    
            //printf("\n");
        ct1++;
        }
      
    for (i = 1; i < n; )
    {
        ok = 0;
        j = i + 1;
        pozi = poz1[i];
        pozj = poz1[j];
        while (a[pozi] != '\0' ||  a[pozj] != '\0')
            if (a[pozi] != a[pozj])
            {
                   viz[j] = 1;
                   ok = 1;
                   break;
                   }
            else 
            {
                 viz[j] = 0;
                 pozi++;
                 pozj++;
                 }
                 
            if (ok) contor++;
            else if (!ok && viz[i]) contor--;
        
            i = j;
        }
    
    printf("%d",contor);
    
return 0;
}