Cod sursa(job #28952)

Utilizator pocaituDavid si Goliat pocaitu Data 8 martie 2007 14:40:30
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<fstream.h>
#include<string.h>
#define nmax 53
#define tmax 503
char m[tmax][nmax],m1[tmax][nmax],s[nmax],A[tmax][nmax],B[tmax][nmax];
int long j,i,n,t,u,a,k,k1,p;
/*void merge_sort(int l, int r)
{
	int m = (l + r) >> 1, i, j, k;
	if (l == r) return;
	merge_sort(l, m);
	merge_sort(m + 1, r);
	for (i=l, j=m+1, k=l; i<=m || j<=r; )
		if (j > r || (i <= m &&strcmp(A[i],A[j])<0))
			strcpy(B[k++],A[i++]);
		else
			strcpy(B[k++],A[j++]);
	for (k = l; k <= r; k++) strcpy(A[k],B[k]);
} */
void merge_sort(int long l, int long r)
{
	int long m = (l + r) >> 1, i, j, k;
	if (l == r) return;
	merge_sort(l, m);
	merge_sort(m + 1, r);
	for (i=l, j=m+1, k=l; i<=m || j<=r; )
		if (j > r || (i <= m &&strcmp(A[i],A[j])< 0))
			strcpy(B[k++],A[i++]);
		else
			strcpy(B[k++],A[j++]);
	for (k = l; k <= r; k++) strcpy(A[k],B[k]);
}





int main()
{ifstream f("amlei.in");
 ofstream g("amlei.out");
 while(f>>s)
  {j=0;
   for(n=t=u=0;s[j]<='9'&&s[j]>='0';j++)
	 n=n*10+s[j]-'0';

   for(f>>s,j=0;s[j]<='9'&&s[j]>='0';j++)
	 t=t*10+s[j]-'0';
	for(f>>s,j=0;s[j]<='9'&&s[j]>='0';j++)
	 u=u*10+s[j]-'0';
	for(i=1;i<=t;i++)
	 {for(j=1;j<=n;j++)
	   {f>>a;
		m[i][0]='1';
		if(a>0)
		  m[i][a]='1';
		else
		  m[i][-a]='0';
		}
	  m[i][j]=NULL;

	  }
	for(i=1;i<=u;i++)
	 {for(j=1;j<=n;j++)
		{f>>a;
		 m1[i][0]='1';
		 if(a>0)
		   m1[i][a]='1';
		 else
		  m1[i][-a]='0';
		 }
	  m1[i][j]=NULL;
	  }
  //ordonez m
  memcpy(A,m,sizeof(A));
   merge_sort(1,t);
  memcpy(m,A,sizeof(A));
  memcpy(A,m1,sizeof(A));
   merge_sort(1,u);
  memcpy(m1,A,sizeof(A));


  //elimin elementele care se repeta
  for(i=1,k=0;i<=t;i++)
   {memcpy(m[++k],m[i],sizeof(m[i]));
	while(!strcmp(m[k],m[i]))
	  i++;
	i--;
	}
  for(i=1,k1=0;i<=u;i++)
   {memcpy(m1[++k1],m1[i],sizeof(m1[i]));
	while(!strcmp(m1[k1],m1[i]))
	  i++;
	i--;
	}


  //compar
  if(k1!=k)
	g<<"NU\n";
  else
	 {for(i=1,p=1;i<=k;i++)
		if(strcmp(m[i],m1[i]))
		  p=0;
	  if(p==1)
	   g<<"DA\n";
	  else
	   g<<"NU\n";
	  }
	}
g.close();
return 0;
}