Cod sursa(job #320528)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 4 iunie 2009 22:05:01
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#include<string.h>
long n,m,p,i,j,aa,x,y,f;
char s[510][60],s1[510][60];
long partit(char a[][60],long st, long dr)
{long i,j,m;
 char piv[60],aa[60];
 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 quicks(char a[][60],long st,long dr)
{long p;
 if(st<dr)
   {p=partit(a,st,dr);
    quicks(a,st,p);
    quicks(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)
     {memset(s[i],0,sizeof(s[i]));
      for(j=1;j<=n;++j)
         {scanf("%ld",&aa);
          if(aa>0)s[i][aa-1]='+';
             else s[i][-1*aa-1]='-';}}
  for(i=1;i<=p;++i)
     {memset(s1[i],0,sizeof(s1[i]));
      for(j=1;j<=n;++j)
         {scanf("%ld",&aa);
          if(aa>0)s1[i][aa-1]='+';
             else s1[i][-1*aa-1]='-';}}
  quicks(s,1,m);
  quicks(s1,1,p);
  x=1;
  y=1;
  f=1;
  while(x<=m&&y<=p)
   {while(!strcmp(s[x+1],s[x]))++x;
    while(!strcmp(s1[y+1],s1[y]))++y;
    if(strcmp(s[x],s1[y])){f=0;break;}
     else{++x;++y;}}
  if(f)printf("DA\n");
  else printf("NU\n");}
 return 0;
}