> 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;
> }
>        
>        
>