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

终于AC, 0ms !!!

Posted by CodesW at 2016-04-14 11:32:51 on Problem 1009
#include <stdio.h>
#include <stdlib.h>

unsigned int width = 0, height = 0 ;
unsigned int pointCnt = 0 ;
struct 
{
	unsigned int val ;
	unsigned int cnt ;
	unsigned int idx ;
}rle[1001] ;
unsigned int rleCnt = 0;
unsigned int edgePoints[9100] = {0} ;
unsigned int edgePointCnt = 0 ;

unsigned int max(unsigned int a, unsigned int b)
{
	return a > b ? a: b ;
}

unsigned int diff(unsigned int a, unsigned int b)
{
	return a > b ? (a - b) : (b - a) ;
}

void swap(unsigned int *a, unsigned int *b)
{
	unsigned int tmp = *a ;
	*a = *b ;
	*b = tmp ;
}

/* 计算变化点周围需要计算的点 */
void egdePointSet(unsigned int changePoint)
{
	if(changePoint >= width + 1)
		edgePoints[edgePointCnt++] = changePoint - width - 1 ;
	if(changePoint >= width)
		edgePoints[edgePointCnt++] = changePoint - width ;
	if(changePoint >= width - 1)
		edgePoints[edgePointCnt++] = changePoint - width + 1 ;
	if(changePoint > 0)
		edgePoints[edgePointCnt++] = changePoint - 1 ;
	
	edgePoints[edgePointCnt++] = changePoint ;
	
	if(changePoint + 1 < pointCnt)
		edgePoints[edgePointCnt++] = changePoint + 1 ;
	if(changePoint + width - 1 < pointCnt)
		edgePoints[edgePointCnt++] = changePoint + width - 1 ;
	if(changePoint + width < pointCnt)
		edgePoints[edgePointCnt++] = changePoint + width ;
	if(changePoint + width + 1 < pointCnt)
		edgePoints[edgePointCnt++] = changePoint + width + 1 ; 
}

/* 获取指定点的边界值 */
unsigned int edgePointValGet(unsigned int point)
{
	unsigned int row = point / width ;
	unsigned int col = point % width ;
	unsigned int pointIdx = 0 ;
	unsigned int maxAbs = 0 ;
	unsigned int arroundPoints[9] = {0} ;
	unsigned int arroundPointCnt = 0 ;
	unsigned int i, j ;

	if(row > 0)
	{
		if(col > 0)
			arroundPoints[arroundPointCnt++] = point - width - 1 ;		
		
		arroundPoints[arroundPointCnt++] = point - width ;		
		
		if(col + 1 < width)
			arroundPoints[arroundPointCnt++] = point - width + 1 ;		
	}

	if(col > 0)
		arroundPoints[arroundPointCnt++] = point - 1 ;
	
	arroundPoints[arroundPointCnt++] = point ;
	pointIdx = arroundPointCnt - 1 ;

	if(col + 1 < width)
		arroundPoints[arroundPointCnt++] = point + 1 ;		
	
	if(row < height - 1)
	{
		if(col > 0)
			arroundPoints[arroundPointCnt++] = point + width - 1 ;		
		
		arroundPoints[arroundPointCnt++] = point + width ;		
		
		if(col + 1 < width)
			arroundPoints[arroundPointCnt++] = point + width + 1 ;		
	}

	j = 1 ;
	for(i = 0; i < arroundPointCnt; i++)
	{
		for(; j < rleCnt; j++)
		{
			if(rle[j].idx > arroundPoints[i])
				break ;
		}
		arroundPoints[i] = rle[j - 1].val ;
	}

	for(i = 0; i < arroundPointCnt; i++)
		maxAbs = max(maxAbs, diff(arroundPoints[pointIdx], arroundPoints[i])) ;

	return maxAbs ;
}

void sort(unsigned int *pointArray, unsigned int size)
{
	unsigned int i = 0, j = 0 ;

	if(size > 2)
		swap(&pointArray[0], &pointArray[rand() % size]) ;

	for(j = 1; j < size; j++)
	{
		if(pointArray[j] < pointArray[0])
		{
			swap(&pointArray[j], &pointArray[i+1]) ;
			i++ ;
		}
	}
	swap(&pointArray[0], &pointArray[i]) ;

	if(i > 1)
		sort(&pointArray[0], i) ;
	if(size - i > 2)
		sort(&pointArray[i+1], size - i - 1) ;
}

int main(int argc, char *argv[])
{
	unsigned int i = 0 ;
	unsigned int lastVal = 0, lastIdx = 0 ;
	unsigned int tmpVal = 0, tmpIdx = 0 ;

	while(scanf("%d", &width) && width)
	{
		printf("%d\r\n", width) ;

		rleCnt = 0 ;
		pointCnt = 0 ;
		edgePointCnt = 0 ;
		while(1)
		{
			scanf("%d %d", &rle[rleCnt].val, &rle[rleCnt].cnt) ;
			if((0 == rle[rleCnt].val) && (0 == rle[rleCnt].cnt))
				break ;
			rle[rleCnt].idx = pointCnt ;
			
			pointCnt += rle[rleCnt].cnt ;
			rleCnt++ ;
		}
		height = pointCnt / width ;

		for(i = 0; i < rleCnt; i++)
			egdePointSet(rle[i].idx) ;
		egdePointSet(pointCnt - 1) ;
		
		sort(edgePoints, edgePointCnt) ;

		lastVal = edgePointValGet(0) ;
		lastIdx = 0 ;
		tmpIdx = lastIdx ;
		for(i = 0; i < edgePointCnt; i++)
		{
			if(edgePoints[i] == tmpIdx)
				continue ;
			tmpIdx = edgePoints[i] ;

			tmpVal = edgePointValGet(edgePoints[i]) ;
			if(tmpVal != lastVal)
			{
				printf("%d %d\r\n", lastVal, edgePoints[i] - lastIdx) ;
				lastVal = tmpVal ;
				lastIdx = edgePoints[i] ;
			}
		}
		printf("%d %d\r\n", lastVal, pointCnt - lastIdx) ;
		printf("0 0\r\n") ;
	}
	printf("0\r\n") ;

	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