Cod sursa(job #2530335)

Utilizator NoemikulcsarKulcsar Noemi Noemikulcsar Data 24 ianuarie 2020 18:03:21
Problema Restante Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin ("restante.in");
ofstream fout("restante.out");
int n,i,z,j,f[36010],ii,ok,nr,aux;
char a[18],v[36010][18],w[36010][18];

int comp(int a, int b)
{
    int i;
    if(v[a][0]>v[b][0])
        return 1;
    else
        if(v[a][0]<v[b][0])
            return -1;
        else
            for(i=1;i<=v[a][0];i++)
                if(v[a][i]>v[b][i])
                    return 1;
                else
                    if(v[a][i]<v[b][i])
                        return -1;
    return 0;
}

void egal1(int k,int a)
{
    int i;
    w[k][0]=v[a][0];
    for(i=1;i<=v[a][0];i++)
        w[k][i]=v[a][i];
    return;
}

void egal2(int a)
{
    int i;
    v[a][0]=w[a][0];
    for(i=1;i<=v[a][0];i++)
        v[a][i]=w[a][i];
    return;
}

void intercls(int st, int mid, int dr)
{
    int i=st, j=mid+1, k=st-1;
    while(i<=mid&&j<=dr)
    {
        if(comp(i,j)==1)
        {
            k++;
            egal1(k, i);
            i++;
        }
        else
        {
            k++;
            egal1(k, j);
            j++;
        }
    }
    for(;i<=mid;i++)
    {
        k++;
        egal1(k, i);
    }
    for(;j<=dr;j++)
    {
        k++;
        egal1(k, j);
    }
    for(i=st;i<=dr;i++)
        egal2(i);
}

void mergesort(int st, int dr)
{
    if(st<dr)
    {
        int mid=(st+dr)/2;
        mergesort(st, mid);
        mergesort(mid+1,dr);
        intercls(st,mid,dr); //funtia primeste sortata secventa de la st la tid, sot sortata
        // pe cea de la mid+1 la dr si le interclaseaza lasandule tot intre st si dr
    }

}

int main ()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a;
        z=0;
        while(a[z]!=0)
            z++;
        sort(a, a+z);
        for(j=1;j<=z;j++)
            v[i][j]=a[j-1];
        v[i][0]=z;
    }
    nr=n;
    mergesort(1, n);
    for(i=1;i<n;i++)
    {
        if(v[i+1][0]==v[i][0])
        {
            ok=1;
            for(j=1;j<=v[i][0];j++)
                if(v[i+1][j]!=v[i][j])
                    ok=0;
            if(ok==1)
            {
                nr--;
                if(f[i]==0)
                {
                    f[i]=-1;
                    nr--;
                }
                f[i+1]=-1;
            }
            aux++;
        }
    }
    fout<<nr;
    fin.close();
    fout.close();
    return 0;
}