Source Code

Problem: 1086  User: yzhw 
Memory: 324K  Time: 47MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
int n,level,*data,*std,map[17][17];
struct point
{
   int ori;
   int id;
};
int min(int a,int b,int c,int d)
{
    if(b<a) a=b;
    if(c<a) a=c;
    if(d<a) a=d;
    return a;
}
int cmp(const void *a,const void *b)
{
   struct point *aa=(struct point *)a;
   struct point *bb=(struct point *)b;
   return aa->ori-bb->ori;
}
void makestd(int now)
{
     if(now*4+1<(4*n*n-1)/3)
     {
        int i;
        makestd(now*4+1);
        makestd(now*4+2);
        makestd(now*4+3);
        makestd(now*4+4);
        struct point list[5];
        for(i=1;i<=4;i++)
        {
         list[i].id=i;
         list[i].ori=std[now*4+i];
        }
        qsort(list+1,4,sizeof(struct point),cmp);
        std[now]=min(std[now*4+1],std[now*4+2],std[now*4+3],std[now*4+4]);
        for(i=1;i<=4;i++) std[now*4+i]=list[i].id;
     }
}
void makemap(int s1,int e1,int s2,int e2,int pos)
{
     if(data[pos]!=-1)
     {
      int i,j;
      for(i=s1;i<=e1;i++)
       for(j=s2;j<=e2;j++)
         map[i][j]=data[pos];
     }
     else
     {
       makemap(s1,(s1+e1)/2,s2,(s2+e2)/2,4*pos+std[4*pos+1]);
       makemap(s1,(s1+e1)/2,(s2+e2)/2+1,e2,4*pos+std[4*pos+2]);
       makemap((e1+s1)/2+1,e1,s2,(s2+e2)/2,4*pos+std[4*pos+3]);
       makemap((s1+e1)/2+1,e1,(s2+e2)/2+1,e2,4*pos+std[4*pos+4]);
     }
}
int main()
{
    int testcase,i;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
       int j,k;
       int tn;
       scanf("%d %d",&n,&tn);
       data=(int *)calloc((4*n*n-1)/3,sizeof(int));
       std=(int *)calloc((4*n*n-1)/3,sizeof(int));
       for(j=1;j<=tn;j++)
       {
         int t1,t2;
         scanf("%d %d",&t1,&t2);
         std[t1]=t2;
       }
       makestd(0);
       scanf("%d",&tn);
       for(j=0;j<(4*n*n-1)/3;j++) data[j]=-1;
       for(j=1;j<=tn;j++)
       {
         int t1,t2;
         scanf("%d %d",&t1,&t2);
         data[t1]=t2;
       }
       makemap(1,n,1,n,0);
       printf("Case %d\n",i);
       printf("\n");
       for(j=1;j<=n;j++)
       {
        for(k=1;k<=n;k++) 
          printf("%4d",map[j][k]);
        printf("\n");
       }
       printf("\n");
       free(std);
       free(data);
    }
    return 0;
}
       
       

• 附毛啊，就知道炫耀 (2636) checkoj 2010-09-06 20:18:22
• Re:哎。。水题，一次AC，附代码 (2636) sd15w2015012893 2017-03-14 08:25:03