Cod sursa(job #360475)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 31 octombrie 2009 17:14:48
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define Nmax 52
#define Tmax 502
#define Smax 100005
using namespace std;

char s[Smax];
int n,t,u,i;
int a[Tmax][Nmax],b[Tmax][Nmax];
int va[Nmax],vb[Nmax];

void prel1( char s[] ){
	int lg,i,nr,z,semn=1,q=0;
   lg=strlen(s); lg--;
   for(nr=1,z=0,i=0;i<lg;++i){
   	if(z == n){
      	z=0;
         nr++;
      }
      if(s[i] == ' ')a[nr][++z]=q*semn,semn=1,q=0;else
      if(s[i]=='-') semn=-1;
      else q=q*10+s[i]-'0';
   }
   if(q) a[nr][++z]=q*semn;
}
void prel2( char s[] ){
	int lg,i,nr,z,semn=1,q=0;
   lg=strlen(s); lg--;
   for(nr=1,z=0,i=0;i<lg;++i){
   	if(z == n){
      	z=0;
         nr++;
      }
      if(s[i] == ' ')b[nr][++z]=q*semn,semn=1,q=0;else
      if(s[i]=='-') semn=-1;
      else q=q*10+s[i]-'0';
   }
   if(q) b[nr][++z]=q*semn;
}

int egal(int v1[], int v2[]){
	int i=1;
   while(v1[i] == v2[i] && i<=n) i++;
   if(i == n+1) return 1;
   return 0;
}
int comp(int v1[], int v2[]){
	int i=1;
   while(v1[i] == v2[i] && i<=n) i++;
   if(i == n+1) return 0;
   if(v1[i] < v2[i] ) return -1;
   return 1;
}
void sort1(int l,int r){
	int i,j;
   int y[Nmax],x[Nmax];
   i=l; j=r; memcpy(x,a[l+(r-l)/2],sizeof(x));
   do{
   	while( comp(a[i],x) < 0 ) i++;
      while( comp(x,a[j]) < 0 ) j--;
      if(i<=j){
      	memcpy(y,a[i],sizeof(y));
         memcpy(a[i],a[j],sizeof(a[i]));
         memcpy(a[j],y,sizeof(y));
         i++; j--;
      }
   } while(i<=j);
   if(i<r) sort1(i,r);
   if(l<j) sort1(l,j);
}
void sort2(int l,int r){
	int i,j;
   int y[Nmax],x[Nmax];
   i=l; j=r; memcpy(x,b[l+(r-l)/2],sizeof(x));
   do{
   	while( comp(b[i],x) < 0 ) i++;
      while( comp(x,b[j]) < 0 ) j--;
      if(i<=j){
      	memcpy(y,b[i],sizeof(y));
         memcpy(b[i],b[j],sizeof(b[i]));
         memcpy(b[j],y,sizeof(y));
         i++; j--;
      }
   } while(i<=j);
   if(i<r) sort2(i,r);
   if(l<j) sort2(l,j);
}

void solve(){
	int i,j,ok;
	for(i=1;i<=t;++i) sort(a[i]+1,a[i]+n+1),va[i]=i;
   for(i=1;i<=u;++i) sort(b[i]+1,b[i]+n+1),vb[i]=i;
   sort1(1,t);
   sort2(1,u);

   for(i=1,j=1,ok=1;i<=t && j<=u && ok;){
      while( egal(a[i],a[i-1]) ) i++;
      while( egal(b[j],b[j-1]) ) j++;
      if( !(egal( a[i], b[j] )) ) ok=0;
      if(i<=t && j<=u ) i++, j++;
   }
      while( egal(a[i],a[i-1]) ) i++;
      while( egal(b[j],b[j-1]) ) j++;
   if( i==t+1 && j==u+1 && ok ) printf("DA\n");
   else printf("NU\n");
}

void read(){
	freopen("amlei.in","r",stdin);
   freopen("amlei.out","w",stdout);
   for( ; scanf("%d%d%d\n",&n,&t,&u) == 3; ){
   	fgets(s,Smax,stdin);
      prel1(s);
      fgets(s,Smax,stdin);
      prel2(s);
      solve();
   }
}

int main(){
	read();

   fclose(stdin); fclose(stdout);
   return 0;
}