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

缩衣节食终于过了……,内存超了3次……

Posted by Web_Board at 2009-01-22 22:41:00 on Problem 1088
#include<stdio.h>
#include<malloc.h>
#define HIGH(x) ((x&0xffff0000)>>16)
#define LOW(x)	(x&0x0000ffff)
#define Get1(x) ((x&0xff000000)>>24)
#define Get2(x) ((x&0x00ff0000)>>16)
#define Get3(x) ((x&0x0000ff00)>>8)
#define Get4(x) (x&0x000000ff)

int cmp(int * ar,int a,int b)
{
	return HIGH(ar[a])-HIGH(ar[b]);
}
void swap(int * array,int a,int b){
    int temp;
	temp=array[a];
	array[a]=array[b];
	array[b]=temp;
}
void qsort(int * array,int low,int high,int Comp(int * array,int ,int ))
{
          int middle,i;
          if(low>=high)
                      return;
          middle=(low+high)/2;
          swap(array,low,middle);
          for(middle=low,i=low+1;i<=high;i++){
                                       if(Comp(array,low,i)>0)
                                               swap(array,++middle,i);
										}
          swap(array,low,middle);
          qsort(array,low,middle-1,Comp);
          qsort(array,middle+1,high,Comp);
}
int getx(int a,int c)
{
	switch(c){
	case 1:
		return Get3(a)-1;
	case 2:case 4:
		return Get3(a);
	case 3:
		return Get3(a)+1;
	default:
		return 0;
	}
}

int gety(int a,int c)
{
	switch(c){
	case 1:case 3:
		return Get4(a);
	case 2:
		return Get4(a)+1;
	case 4:
		return Get4(a)-1;
	default:
		return 0;
	}
}

int main()
{
	int R,C,* * hill,* * va,x,y,i,j,h,m;
	int * rank;
	scanf("%d %d",&R,&C);
	h=R*C;
	rank=(int *)malloc(sizeof(int)*(h+1));
	
	hill=(int **)malloc(sizeof(int *)*(R+1));
	for(i=1;i<=R;i++)
		hill[i]=(int *)malloc(sizeof(int )*(C+1));
	va=(int **)malloc(sizeof(int *)*(R+1));
	for(i=1;i<=R;i++)
		va[i]=(int *)malloc(sizeof(int )*(C+1));
	for(x=1,i=1;x<=R;x++)
		for(y=1;y<=C;y++,i++){
			scanf("%d",&hill[x][y]);
			va[x][y]=1;
			rank[i]=0;
			rank[i]|=hill[x][y]<<16;
			rank[i]|=x<<8;
			rank[i]|=y;
		}
	qsort(rank,1,h,cmp);
	for(i=1,m=1;i<=h;i++){
		for(j=1;j<=4;j++){
			x=getx(rank[i],j);
			y=gety(rank[i],j);
			if(x>R||y>C||!x||!y)
				continue;
			if(hill[x][y]<(signed)HIGH(rank[i])){
				if(va[Get3(rank[i])][Get4(rank[i])]<=va[x][y])
					va[Get3(rank[i])][Get4(rank[i])]=va[x][y]+1;
			}
		}
		if(m<va[Get3(rank[i])][Get4(rank[i])])
			m=va[Get3(rank[i])][Get4(rank[i])];
	}
	printf("%d",m);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator