Cod sursa(job #213637)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 10 octombrie 2008 18:33:19
Problema Amlei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long n,m,p,i,j,a[1000][1000],b[1000][1000],l,f;
char sa[1000][1000],sb[1000][1000];
long partit(long a[ ],long st, long dr)
{long i,j,m,piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i]<piv&&i<j);
   do{--j;} while(a[j]>piv&&j>i);
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(long a[ ],long st,long dr)
{long p;
 if (st<dr)
   {p=partit(a,st,dr);
	quicks(a,st,p);
	quicks(a,p+1,dr);
   }
}
long partiti(char a[ ][1000],long st, long dr)
{long i,j,m;
 char piv[1000],aa[1000];
 m=(st+dr)/2;
 strcpy(piv,a[m]);
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(strcmp(a[i],piv)<0);
   do{--j;} while(strcmp(a[j],piv)>0);
   if (i<j)
	 {strcpy(aa,a[i]);strcpy(a[i],a[j]);strcpy(a[j],aa);}
	   else
	 return j;
  }
}
void qsort(char a[ ][1000],long st,long dr)
{long p;
 if (st<dr)
   {p=partiti(a,st,dr);
    qsort(a,st,p);
    qsort(a,p+1,dr);
   }
}
int main()
{
 freopen("amlei.in","r",stdin);
 freopen("amlei.out","w",stdout);
 while(scanf("%ld%ld%ld",&n,&m,&p)!=EOF)
 {
  for(i=1;i<=m;++i)
     {for(j=1;j<=n;++j)scanf("%ld",&a[i][j]);
     quicks(a[i],1,n);
     l=-1;
     for(j=1;j<=n;++j)
        {
         if(a[i][j]<0)sa[i][++l]='-';
         if(a[i][j]>=10)sa[i][++l]=(char)(a[i][j]/10)-'0';
         sa[i][++l]=(char)abs(a[i][j])+'0';
        }
      sa[i][++l]=0;
                    
     }
  for(i=1;i<=p;++i){for(j=1;j<=n;++j)scanf("%ld",&b[i][j]);
                    quicks(b[i],1,n);
                    l=-1;
                    for(j=1;j<=n;++j)
                       {
                        if(b[i][j]<0)sb[i][++l]='-';
                        if(b[i][j]>=10)sb[i][++l]=(char)(b[i][j]/10)-'0';
                        sb[i][++l]=(char)abs(b[i][j])+'0';
                       }
                    sb[i][++l]=0;
                   }
  qsort(sa,1,m);
  qsort(sb,1,p);
  f=1;
  j=1;
  if(m<p)
  for(i=1;i<=m;++i)
     {if(strcmp(sb[j],sa[i])){f=0;break;}
      while(!strcmp(sb[++j],sa[i])){};
     }
  else
  for(i=1;i<=p;++i)
     {if(strcmp(sb[j],sa[i])){f=0;break;}
      while(!strcmp(sa[++j],sb[i])){};
     }
  
  if(f)printf("DA\n");
  else printf("NU\n");
 }
 return 0;
}