Cod sursa(job #19719)

Utilizator moga_florianFlorian MOGA moga_florian Data 19 februarie 2007 21:14:23
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
using namespace std;
#include<fstream>
#include<stdio.h>
#include<string.h>

int a[505][55],b[505][55],aux[55],ra[205],rb[505];
int v[105],n;
char s[2000];

int compa(int i,int j)
{
int k=1;
while(k<=n&&a[i][k]==a[j][k]) k++;
if(k>n) return 0;
if(a[i][k]<a[j][k])
    return -1;
return 1;    
}

int compb(int i,int j)
{
int k=1;
while(k<=n&&b[i][k]==b[j][k]) k++;
if(k>n) return 0;
if(b[i][k]<b[j][k]) return -1;
return 1;    
}

int comp(int i,int j)
{
int k=1;
while(k<=n&&a[i][k]==b[j][k]) k++;
if(k>n) return 1;
return 0;    
}

void inta(int i,int j)
{
memcpy(aux,a[i],sizeof aux);
memcpy(a[i],a[j],sizeof aux);
memcpy(a[j],aux,sizeof aux);     
}

void intb(int i,int j)
{
memcpy(aux,b[i],sizeof aux);
memcpy(b[i],b[j],sizeof aux);
memcpy(b[j],aux,sizeof aux);          
}

int main()
{
ifstream fin("amlei.in");
FILE *fout=fopen("amlei.out","w");
     
int u,t,i,j,k;

while(fin>>n)
 {
 memset(a,0,sizeof a);
 memset(b,0,sizeof b);

 fin>>u>>t;
 
 for(i=1;i<=u;i++)
   for(j=1;j<=n;j++)
      {
      fin>>a[i][j];
      a[i][j]+=n;                    
      }
      
 for(i=1;i<=t;i++)
    for(j=1;j<=n;j++)
       {
       fin>>b[i][j];
       b[i][j]+=n;  
       }            
          
 //sort bucati
 for(i=1;i<=u;i++)
    {
    memset(v,0,sizeof v);
    for(j=1;j<=n;j++)
       v[a[i][j]]=1;
    k=0;
    for(j=0;j<=2*n;j++)
       if(v[j])
         a[i][++k]=j;
    }

 for(i=1;i<=t;i++)
    {
    memset(v,0,sizeof v);
    for(j=1;j<=n;j++)
       v[b[i][j]]=1;
    k=0;
    for(j=0;j<=2*n;j++)
       if(v[j])
         b[i][++k]=j;
    }
    
 //sort fashii
 for(i=1;i<=u;i++)
    {
    j=i;
    while(j/2&&compa(j/2,j)<0)
          {
          inta(j/2,j);                    
          j/=2;
          }              
    }
 i=u;
 while(i>1)
  {
  inta(1,i);
  i--;
  
  j=1;
  while(1)
    {
    k=2*j;
    if(k>i) break;
    if(k+1<=i&&compa(k+1,k)>0) k++;
    if(compa(j,k)>=0) break;
    
    inta(j,k);
    j=k;      
    }         
  }
  
 for(i=1;i<=t;i++)
    {
    j=i;
    while(j/2&&compb(j/2,j)<0)
       {
       intb(j/2,j);
       j/=2;                       
       }              
    }
 i=t;
 while(i>1)
   {
   intb(1,i);
   i--;
   
   j=1;
   while(1)
    {
    k=j<<1;
    if(k>i) break;
    if(k+1<=i&&compb(k+1,k)>0) k++;
    if(compb(j,k)>=0) break;
    
    intb(j,k);
    j=k;       
    }        
   }
   
// memset(ra,0,sizeof ra);
// memset(rb,0,sizeof rb);
 for(i=2;i<=u;i++)
    if(compa(i,i-1)==0)
      {
      for(k=i;k<u;k++)
          memcpy(a[k],a[k+1],sizeof a[k]);
      u--;
      i--;                 
      }
    
    
 for(i=2;i<=t;i++)
    if(compb(i,i-1)==0)
      {
      for(k=i;k<t;k++)
          memcpy(b[k],b[k+1],sizeof b[k]);
      t--;
      i--;                       
      }
    
 if(u!=t)
    fprintf(fout,"NU\n");
 else
   {
   i=1;
   while(i<=u&&comp(i,i)) i++;
   if(i>u) fprintf(fout,"DA\n");
   else
    fprintf(fout,"NU\n");                      
   }
    
 /*
 i=1;j=1;
 while(i<=u&&j<=t)
   {
   if(ra[i]==0&&rb[j]==0)
      {
      if(comp(i,j))
          i++,j++;
      else
         break;               
      }
   else
     {
     if(ra[i]==1)
       i++;
     if(rb[j]==1)
       j++;
     }           
   }
   
 while(i<=u&&ra[i]) i++;
 while(j<=t&&rb[j]) j++;
 
 if(i>u&&j>t)
    fprintf(fout,"DA\n");
 else
    fprintf(fout,"NU\n");          
 */
    
 }
 
fin.close();
fclose(fout);
return 0;    
}