Cod sursa(job #1553665)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 20 decembrie 2015 11:59:03
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>
#include <algorithm>
#define MAXN 36000
#define MAXL 16
char mat[MAXN][MAXL],pivot[MAXL];
int v[MAXN];
using namespace std;
inline int getmax(int a,int b){
    if(a>b) return a;
    return b;
}
inline int comp(char *v1,char *v2,int x1,int x2){
    if(x1<x2) return 1;
    if(x1>x2) return 0;
    if(x1==x2){
        int i=0;
        while(i<x1&&v1[i]==v2[i])
            i++;
        if(i==x1)
            return 0;
        if(v1[i]>v2[i])
            return 0;
        else
            return 1;
    }

}
void myqsort(int begin,int end){
    int b=begin,e=end,nr=v[(b+e)/2],i,aux1;
    char aux;
    for(i=0;i<v[(b+e)/2];i++)
        pivot[i]=mat[(b+e)/2][i];
    while(b<=e){
        while(comp(mat[b],pivot,v[b],nr)==1) b++;
        while(comp(pivot,mat[e],nr,v[e])==1) e--;
        if(b<=e){
            for(i=0;i<getmax(v[b],v[e]);i++){
                aux=mat[b][i];
                mat[b][i]=mat[e][i];
                mat[e][i]=aux;
            }
            aux1=v[b];
            v[b]=v[e];
            v[e]=aux1;
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e);
    if(b<end) myqsort(b,end);
}
inline int egal(int lin){
    int i=0;
    if(v[lin]!=v[lin+1])
        return 0;
    else{
        while(i<v[lin]&&mat[lin][i]==mat[lin+1][i])
            i++;
        return (i==v[lin]);
    }
}
int main(){
    FILE*fi,*fout;
    int i,j,n,con;
    char a;
    fi=fopen("restante.in" ,"r");
    fout=fopen("restante.out" ,"w");
    fscanf(fi,"%d" ,&n);
    a=fgetc(fi);
    for(i=0;i<n;i++){
        a=fgetc(fi);
        while(a>='a'&&a<='z'){
            mat[i][v[i]++]=a;
            a=fgetc(fi);
        }
        sort(mat[i],mat[i]+v[i]);
    }
    myqsort(0,n-1);
    i=con=0;
    while(i<n){
        j=i;
        while(j<n-1&&egal(j)==1)
            j++;
        if(i==j)
           con++;
        i=j+1;
    }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}