Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 哎。。水题，一次AC，附代码

Posted by yzhw at 2009-05-06 02:16:00 on Problem 1086
```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;
}

```

Followed by: