Cod sursa(job #1811319)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 21 noiembrie 2016 09:30:44
Problema Restante Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <algorithm>
#include <bitset>

using namespace std;
int a[36001][17];
int b[36001][17];
int ff[30];
int compar (int x,int y){
    for (int i=0;i<=a[x][0];i++){
        if (a[x][i]>a[y][i])
            return 0;
        else if (a[x][i]<a[y][i])
            return 1;
    }
    return 2;
}
void muta (int x,int y){
    for (int i=0;i<=a[y][0];i++)
        b[x][i]=a[y][i];
}
void transf (int st,int dr){
    for (int i=st;i<=dr;i++)
        for (int j=0;j<=b[i][0];j++)
            a[i][j]=b[i][j];
}
void interclas (int st,int mid,int dr){
    int i,j,k=0;
    i=st;
    j=mid+1;
    while (i<=mid && j<=dr){
        if (compar (i,j)){
            k++;
            muta (k,i);
            i++;
        }
        else {
            k++;
            muta (k,j);
            j++;
        }
    }
    while (i<=mid){
        k++;
        muta (k,i);
        i++;
    }
    while (j<=dr){
        k++;
        muta (k,j);
        j++;
    }
    transf (st,dr);
}
void merge (int st,int dr){
    if (st<dr){
        int mid=(st+dr)/2;
        merge (st,mid);
        merge (mid+1,dr);
        interclas (st,mid,dr);
    }
}
int main()
{
    FILE *fin=fopen ("restante.in","r");
    FILE *fout=fopen ("restante.out","w");
    int n,i,uni,st,l;
    char c;
    fscanf (fin,"%d\n",&n);
    for (i=1;i<=n;i++){
        c=fgetc (fin);
        while (c!='\n'){
            l=c-'a'+1;
            ff[l]++;
            c=fgetc (fin);
        }
        for (int j=1;j<30;j++){
            while (ff[j]){
                a[i][++a[i][0]]=j;
                ff[j]--;
            }
        }
    }
    merge (1,n);
    uni=0;
    st=0;
    for (i=1;i<=n;i++){
        if (compar(i,i-1)!=2){
            uni++;
            st=0;
        }
        else
            if (st==0){
                st=1;
                uni--;
            }
    }
    fprintf (fout,"%d",uni);
    return 0;
}