Cod sursa(job #1722390)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 27 iunie 2016 22:48:38
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <cstring>
#define B 2
#define MOD1 666013
#define MOD2 666019
#define MAXN 50
#define MAXA 500
int v[MAXN+1], c[MAXA+1], val[MAXA+1], next[MAXA+1], lista[MOD1];
int main(){
    int n, a, b, i, j, r1, r2, x, s, t, p;
    FILE *fin, *fout;
    fin=fopen("amlei.in", "r");
    fout=fopen("amlei.out", "w");
    while(fscanf(fin, "%d%d%d", &n, &a, &b)!=EOF){
        memset(lista, 0, sizeof lista);
        s=0;
        for(i=1; i<=a; i++){
            for(j=1; j<=n; j++){
                fscanf(fin, "%d", &x);
                if(x<0) v[-x]=1;
                else v[x]=0;
            }
            r1=r2=0;
            for(j=1; j<=n; j++){
                r1=(r1*B+v[j])%MOD1;
                r2=(r2*B+v[j])%MOD2;
            }
            p=lista[r1];
            while((p)&&(val[p]!=r2)) p=next[p];
            if(p==0){
                s++;
                c[i]=1;
                val[i]=r2;
                next[i]=lista[r1];
                lista[r1]=i;
            }
        }
        t=1;
        for(i=1; i<=b; i++){
            for(j=1; j<=n; j++){
                fscanf(fin, "%d", &x);
                if(x<0) v[-x]=1;
                else v[x]=0;
            }
            r1=r2=0;
            for(j=1; j<=n; j++){
                r1=(r1*B+v[j])%MOD1;
                r2=(r2*B+v[j])%MOD2;
            }
            p=lista[r1];
            while((p)&&(val[p]!=r2)) p=next[p];
            if(p==0) t=0;
            else{
                s-=c[p];
                c[p]=0;
            }
        }
        if(s==0) t=1;
        if(t==1) fprintf(fout, "DA\n");
        else fprintf(fout, "NU\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}