Cod sursa(job #250283)

Utilizator Andrei200Andrei200 Andrei200 Data 30 ianuarie 2009 15:16:34
Problema Amlei Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2*25000+1

int frecv1[Nmax];
int frecv2[Nmax];
int frecv3[Nmax];
int frecv4[Nmax];
int a1[Nmax];
int b1[Nmax];
int a[Nmax/2];
int b[Nmax/2];
int n,u,t,ok;
int nr1,nr2;

#define frecv1 (frecv1+25000)
#define frecv2 (frecv2+25000)
#define frecv3 (frecv3+25000)
#define frecv4 (frecv4+25000)

void qsort(int l, int r, int C[],int N)   
{   
 int i,j,x,y;   
 i=l;   
 j=r;   
 x=C[(l+r)>>1];   
 do  
    {   
    while ((C[i]<x)&&(i<N)) ++i;   
    while ((x<C[j])&&(j>1)) --j;   
    if (i<=j)   
        {   
        y=C[i];   
        C[i]=C[j];   
        C[j]=y;   
        ++i;   
        --j;   
        }   
    }   
 while (i<=j);   
 if (l<j) qsort(l,j,C,N);   
 if (i<r) qsort(i,r,C,N);   
}   

int max(int a, int b)
{
    if (a>b) return a;
    return b;
}

int main()
{
    int i;
    freopen("amlei.in","r",stdin);
    freopen("amlei.out","w",stdout);
    while(!feof(stdin))
    {
        memset(frecv1,0,sizeof(frecv1));
        memset(frecv2,0,sizeof(frecv2));
        memset(frecv3,0,sizeof(frecv3));
        memset(frecv4,0,sizeof(frecv4));
        scanf("%d %d %d", &n,&t,&u);
        for (i=1;i<=n*t;++i)
              scanf("%d", &a[i]);
        for (i=1;i<=n*u;++i)
              scanf("%d", &b[i]);
        for (i=1;i<=n*t/2;++i)
              frecv1[a[i]]++;
        for (i=n*t/2+1;i<=n*t;++i)
              frecv2[a[i]]++;       
        for (i=1;i<=n*u/2;++i)
              frecv3[b[i]]++;
        for (i=n*u/2+1;i<=n*u;++i)
              frecv4[b[i]]++;      
        for (i=1;i<=n*t;++i)
              if (frecv1[i]>0 && frecv2[n*t/2+i]>0)
                   frecv2[n*t/2+i]=0;
        for (i=1;i<=n*u;++i)
              if (frecv3[i]>0 && frecv4[n*u/2+i]>0)
                   frecv4[n*u/2+i]=0; 
        nr1=0;  
        for (i=1;i<=n*t/2;++i)
              if (frecv1[i]>0)
                  a1[++nr1]=i;   
        for (i=n*t/2+1;i<=n*t;++i)
              if (frecv2[i]>0)
                  a1[++nr1]=i;
        nr2=0;
        for (i=1;i<=n*u/2;++i)
              if (frecv3[i]>0)
                  b1[++nr2]=i;
        for (i=n*u/2+1;i<=n*u;++i)
              if (frecv4[i]>0)
                  b1[++nr2]=i;
        qsort(-n*t,n*t,a1,nr1);
        qsort(-n*u,n*u,b1,nr2);
        ok=1;
        if (nr1!=nr2)
             ok=0;
             else
             {
        for (i=1;i<=max(nr1,nr2);++i)
             if (a1[i]!=b1[i])
                 {
                        ok=0;
                        break;
                 }
            }    
        if (ok) printf("DA\n");
            else printf("NU\n");
     }
     return 0;
}