Cod sursa(job #1551419)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 15 decembrie 2015 20:50:48
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <algorithm>
#define B 29
#define MOD1 666019
#define MOD2 4643237
#define MAXE 36000
#define MAXN 16
int v[MAXN], next[MAXE+1], val[MAXE+1], ok[MAXE+1], lista[MOD1];
int main(){
    int e, a, b, n, i, ans, p, k;
    char ch;
    FILE *fin, *fout;
    fin=fopen("restante.in", "r");
    fout=fopen("restante.out", "w");
    fscanf(fin, "%d ", &e);
    k=0;
    ans=0;
    for(; e; e--){
        ch=fgetc(fin);
        a=b=n=0;
        while(ch!='\n'){
            v[n++]=ch;
            ch=fgetc(fin);
        }
        std::sort(v, v+n);
        for(i=0; i<n; i++){
            a=(a*B+v[i]-'a'+1)%MOD1;
            b=(b*B+v[i]-'a'+1)%MOD2;
        }
        p=lista[a];
        while((p)&&(val[p]!=b)){
            p=next[p];
        }
        if(p){
            ans-=ok[p];
            ok[p]=0;
        }else{
            k++;
            val[k]=b;
            next[k]=lista[a];
            lista[a]=k;
            ok[k]=1;
            ans++;
        }
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}