Cod sursa(job #472253)

Utilizator darrenRares Buhai darren Data 23 iulie 2010 16:08:51
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

const int SIZE = 36001;

ifstream fin("restante.in");
ofstream fout("restante.out");

void Read();
void Solve();
void Write();

int n, res, in[SIZE], len[SIZE];
char v[SIZE][18];

int cmp(int i1, int i2)
{
    if (len[in[i1]] != len[i2])
        return len[in[i1]] < len[i2];
    for (int i = 0; i < len[in[i1]]; ++i)
        if (v[in[i1]][i] != v[i2][i])
            return v[in[i1]][i] < v[i2][i];
    return 2;
}
void Sort(int st, int dr) //cmp(i, j) = 1 <==> i < j
{
    int i = st - 1, j = dr + 1;
    int piv = in[st];

    do
    {
        do { ++i; } while (cmp(i, piv) == 1 && i <= n);
        do { --j; } while (cmp(j, piv) == 0 && j >= 1);
        if (i <= j) swap(in[i], in[j]);
    } while (i <= j);
    if (st < j) Sort(st, j);
    if (i < dr) Sort(i, dr);
}

int main()
{
    Read();
    Solve();
    Write();
}

void Read()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        sort(v[i], v[i] + strlen(v[i]));

        in[i] = i;
        len[i] = strlen(v[i]);
    }
}

void Solve()
{
    Sort(1, n);
    for (int i = 1; i <= n; ++i)
        if ( (i == 1 || strcmp(v[in[i]], v[in[i - 1]]) != 0) && (i == n || strcmp(v[in[i]], v[in[i + 1]]) != 0) )
            ++res;
}

void Write()
{
    fout << res;
}