Назад к лучшим решениям Status: AC, problem ZRIS, contest ZEL06. By werewolf (Werewolf), 2006-02-25 06:02:26.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include <time.h>
typedef struct _WIDTHCOUNT
{
	unsigned short width;
	unsigned short count;
}WIDTHCOUNT, *PWIDTHCOUNT;
#define MAXWIDTH 1000
WIDTHCOUNT Rectangles[MAXWIDTH+1][MAXWIDTH+1];
unsigned short SumElements[MAXWIDTH +1];
unsigned short BestSum[MAXWIDTH +3];
unsigned int Square[MAXWIDTH+1][MAXWIDTH+1];
unsigned int nUsedElements;
unsigned int nCountRect;
 
 
 
int __inline comparewidth( const void *arg1, const void *arg2 )
{
	return ((PWIDTHCOUNT)arg1)->width == ((PWIDTHCOUNT)arg2)->width?0:((PWIDTHCOUNT)arg1)->width < ((PWIDTHCOUNT)arg2)->width?-1:1;
}
int __inline AddRectangle(unsigned short size1, unsigned short size2, unsigned short count)
{
WIDTHCOUNT wc, *pwc, *pwc1;
	unsigned int num;
	wc.width = size1;
	num = Rectangles[0][0].count;
	pwc = lfind(&wc, &Rectangles[1], &num, sizeof(Rectangles[0]), comparewidth);
	if(!pwc)
	{
		Rectangles[0][0].count++;
		Rectangles[Rectangles[0][0].count][0].width = size1;
		Rectangles[Rectangles[0][0].count][0].count = 1;
		Rectangles[Rectangles[0][0].count][1].width = size2;
		Rectangles[Rectangles[0][0].count][1].count = count;
	}else
	{
		wc.width = size2;
		num = pwc->count;
		pwc1 = lfind(&wc, &pwc[1], &num, sizeof(Rectangles[0][0]), comparewidth);
		if(!pwc1)
		{
			pwc->count ++;
			pwc[pwc->count].width = size2;
			pwc[pwc->count].count = count;
		}else
		{
			pwc1->count += count;
		}
	}
	if(size2 == size1)
		return 1;
	wc.width = size2;
	num = Rectangles[0][0].count;
	pwc = lfind(&wc, &Rectangles[1], &num, sizeof(Rectangles[0]), comparewidth);
	if(!pwc)
	{
		Rectangles[0][0].count++;
		Rectangles[Rectangles[0][0].count][0].width = size2;
		Rectangles[Rectangles[0][0].count][0].count = 1;
		Rectangles[Rectangles[0][0].count][1].width = size1;
		Rectangles[Rectangles[0][0].count][1].count = count;
	}else
	{
		wc.width = size1;
		num = pwc->count;
		pwc1 = lfind(&wc, &pwc[1], &num, sizeof(Rectangles[0][0]), comparewidth);
		if(!pwc1)
		{
			pwc->count ++;
			pwc[pwc->count].width = size1;
			pwc[pwc->count].count = count;
		}else
		{
			pwc1->count += count;
		}
	}	
/*	
	int i, j;
 
	for(i = 1; i<=Rectangles[0][0].count;i++)
	{
		if(Rectangles[i][0].width == size1)
			break;
	}
	if(i == Rectangles[0][0].count+1)
	{
		Rectangles[i][0].width = size1;
		Rectangles[0][0].count++;
	}
 
	for(j = 1; j<=Rectangles[i][0].count;j++)
	{
		if(Rectangles[i][j].width == size2)
			break;
	}

	if(j == Rectangles[i][0].count+1)
	{
		Rectangles[i][j].width = size2;
		Rectangles[i][j].count = count;
		Rectangles[i][0].count++;
	}else
		Rectangles[i][j].count += count;	
 
	if(size2 == size1)
		return 1;
	
 
	for(i = 1; i<=Rectangles[0][0].count;i++)
	{
		if(Rectangles[i][0].width == size2)
			break;
	}
	if(i == Rectangles[0][0].count+1)
	{
		Rectangles[i][0].width = size2;
		Rectangles[0][0].count++;
	}
 
	for(j = 1; j<=Rectangles[i][0].count;j++)
	{
		if(Rectangles[i][j].width == size1)
			break;
	}
 
	if(j == Rectangles[i][0].count+1)
	{
		Rectangles[i][j].width = size1;
		Rectangles[i][j].count = count;
		Rectangles[i][0].count++;
	}else
		Rectangles[i][j].count += count;
*/
	return 1;
}
int SortRectangles()
{
	int i;
	qsort(&Rectangles[1], Rectangles[0][0].count, sizeof(Rectangles[1]), comparewidth);
	for(i = 1; i<Rectangles[0][0].count+1;i++)
	{
		qsort(&Rectangles[i][1], Rectangles[i][0].count, sizeof(Rectangles[0][0]), comparewidth);
	}
	return 1;
}
void __inline DeleteArray(int pos)
{
	memmove(&Rectangles[pos], &Rectangles[pos+1], (Rectangles[0][0].count-pos)*sizeof(Rectangles[0]));
	Rectangles[0][0].count--;
 
}
void __inline DeleteElement(int pos1, int pos2)
{
	if(!--Rectangles[pos1][pos2].count)
	{
		memmove(&Rectangles[pos1][pos2], &Rectangles[pos1][pos2+1], (Rectangles[pos1][0].count-pos2)*sizeof(Rectangles[0][0]));
		if(!--Rectangles[pos1][0].count)
			DeleteArray(pos1);
	}
}
int __inline FindElement(unsigned short width, int HeightPos, int MaxWidthPos)
{
	WIDTHCOUNT wc, *pwc;
	if(Rectangles[HeightPos][MaxWidthPos].width < width)
		return 0;
	wc.width = width;
	if((pwc = (PWIDTHCOUNT)bsearch(&wc, &Rectangles[HeightPos][1], MaxWidthPos, sizeof(WIDTHCOUNT), comparewidth)) &&
		pwc->count)
		return ((unsigned int)pwc - (unsigned int)&Rectangles[HeightPos][0])/sizeof(WIDTHCOUNT);
	else
		return 0;
}
int __inline FindArray(unsigned short height, int MaxHeightPos)
{
	WIDTHCOUNT wc, *pwc;
	if(Rectangles[MaxHeightPos][0].width < height)
		return 0;
 
	wc.width = height;
	if((pwc = (PWIDTHCOUNT)bsearch(&wc, &Rectangles[1], MaxHeightPos, sizeof(Rectangles[0]), comparewidth)) &&
		pwc->count)
		return ((unsigned int)pwc - (unsigned int)&Rectangles[0])/sizeof(Rectangles[0]);
	else
		return 0;
}
int __inline UpdateBestSum(unsigned short SumPart, int count, int height)
{
	if(BestSum[0]>SumPart || (BestSum[0]==SumPart && BestSum[1] > count))
	{
 
		memcpy(BestSum+3, SumElements, count*sizeof(SumElements[0]));
		BestSum[0] = SumPart;
		BestSum[1] = count;
		BestSum[2] = height;
		return 1;
	}
	return 0;
	
}
unsigned short CanCompleteSum(unsigned short pos, unsigned short sum, int maxpos)
{
	int i, isless = 1, ismore = 0, fullsum = 0;
	for(i = 1;i<=maxpos;i++)
	{
		if(!Rectangles[pos][i].count)
			continue;
		if(isless && Rectangles[pos][i].width<=sum)
			isless = 0;
 
		fullsum += Rectangles[pos][i].width*Rectangles[pos][i].count;
 
	}
	return isless?0:fullsum>=sum?sum:fullsum;
}
 
int FindSum(int MaxItems, unsigned short NeedSum, unsigned short HeightPos, unsigned short MaxWidthPos, int ItemNumber)
{
	int tmp, finded = 0;
	int SumPart, i;
 
	if(!MaxWidthPos)
		return -1;
 
	if(MaxItems == 0)
		return 0;
 
	
	if(FindElement(NeedSum, HeightPos, MaxWidthPos))
	{
		SumElements[ItemNumber] = NeedSum;
		UpdateBestSum(0, ItemNumber+1, Rectangles[HeightPos][0].width);
		return 1;
	}
 
	for(i = MaxWidthPos;i>0;i--)
	{
		SumPart = NeedSum-Rectangles[HeightPos][i].width;
		if(!Rectangles[HeightPos][i].count || SumPart <= 0)
			continue;
 
		tmp = Rectangles[HeightPos][i].width;
		Rectangles[HeightPos][i].count--;
		SumElements[ItemNumber] = tmp;
		
		UpdateBestSum(SumPart, ItemNumber+1, Rectangles[HeightPos][0].width);
 
		finded = FindSum(MaxItems - 1, SumPart, HeightPos, Rectangles[HeightPos][i].count?i:i-1, ItemNumber+1);
		Rectangles[HeightPos][i].count++;
 
		if(finded)
			return finded;
	}
 
	return 0;
}
void DeleteItem(unsigned short width, unsigned short height)
{
	unsigned pos1, pos2;
	pos1 = FindArray(height, Rectangles[0][0].count);
	if(pos1)
	{
		pos2 = FindElement(width, pos1, Rectangles[pos1][0].count);
		if(pos2)
		{
			DeleteElement(pos1, pos2);
		}
	}
	if(width == height)
		return;
	pos1 = FindArray(width, Rectangles[0][0].count);
	if(pos1)
	{
		pos2 = FindElement(height, pos1, Rectangles[pos1][0].count);
		if(pos2)
		{
			DeleteElement(pos1, pos2);
		}
	}
}
 
int FindNextPlace(unsigned short xmax, unsigned short  ymax, unsigned short * px, unsigned short *py , unsigned short * psx, unsigned short * plsy, unsigned short * prsy)
{
	short x = xmax, y = 0, dx = 0, dy = 0, sx = 0, sy = 0, rsy = 0, lsy = 0;
	short curx = xmax, cury = 0, cursx = 0, curlsy = 0, currsy = 0;
 
	if(!Square[x-1][y])
	{
		x--;
		dx = -1;
		curx = x;
		cury = y;
		cursx = 1;
	}else
	{
		dy = 1;
	}
	*py = ymax;
	*px = 0;
	*psx = 0;
	while(x > 0)
	{
		//step down
		if(dy !=1 && y>0 && !Square[x][y-1])
		{
			if(dx == -1)
				currsy = 0;
//			if(dy == -1)
				currsy++;
			cursx = 1;
			dx = 0;
			dy = -1;
		}else 
		//step left
		if(x>0 && !Square[x-1][y])
		{			
			if(dx == -1)
				cursx;
			else if(dy == -1)
			{
				curx = x;
				cury = y;
				
			}else if(dy == 1)
			{
				//check for optimal
				if(cursx && (*py > cury || (*py == cury && *psx > cursx)))
				{
					*px = curx - cursx + 1;
					*py = cury;
					*psx = cursx;
					*plsy = curlsy;
					*prsy = currsy;	
				}
				cursx = 0;
				curlsy = 0;
				currsy = 0;
				curx = x-1;
				cury = y;
			}
			cursx++;
			dx = -1;
			dy = 0;
		}else 
		//step up
		if(y<ymax)
		{
			if(dy == -1)
			{
				curx = x;
				cury = y;
				
			}
//			if(dy == 1)
				curlsy++;
			dx = 0;
			dy = 1;
		}else
		{
			//something wrong
			break;
		}
		x+=dx;
		y+=dy;
 
	}
	//check for optimal
	if(*py > cury || (*py == cury && *psx > cursx))
	{
		*px = curx - cursx + 1;
		*py = cury;
		*psx = cursx;
		*plsy = curlsy;
		*prsy = currsy;	
	}
	if(*psx)
	{
		if(*plsy == 0)
		{
			*plsy = ymax - *py;
		}
		if(*prsy == 0)
		{
			*prsy = ymax - *py;
		}
		if(*plsy>*prsy)
		{
			cury = *plsy;
			*plsy = *prsy;
			*prsy = cury;
		}
		return 1;
	}
	else
		return 0;
}
void FillSquare(unsigned short x, unsigned short y, unsigned short sx, unsigned short sy, int stub)
{
	int i, j;
	unsigned int val;
	if(stub)
	{
		val = -1;
	}else
	{
		val = sx;
		val=(val<<16)+sy;
	}
	for(i = x;i < x+sx;i++)
	{
		for(j=y;j<y+sy;j++)
		{
			Square[i][j] = val;
		}
 
	}
}
 
int __inline SmartFindSum(unsigned short NeedSum, unsigned short HeightPos)
{
	int i, MaxItems = 0;
	for(i=0;i<Rectangles[HeightPos][0].count;i++)
	{
		MaxItems += Rectangles[HeightPos][i].count;
	}
	if(!MaxItems)
		return 0;
	if(FindSum(MaxItems, NeedSum, HeightPos, Rectangles[HeightPos][0].count,0) == 1)
	{
		return 1;
	}
	return 0;
}
void __inline ZeroBestSum()
{
	BestSum[0] = 1000;
	BestSum[1] = 0;
	BestSum[2] = 0;
}
void Prepare(int max)
{
	int i ,j;
	for(i = 0;i<=max;i++)
	{
		for(j=0;j<=max;j++)
		{
			Square[i][j]=0;
		}
 
	}
	for(i = nCountRect;i>=0;i--)
	{
		Rectangles[i][0].count=0;
		Rectangles[i][0].width=0;
	}
 
	nUsedElements = 0;
	ZeroBestSum();
 
}
int FindRectangle(unsigned short Height, unsigned short Width)
{
	unsigned short pos;
	pos = FindArray(Height, Rectangles[0][0].count);
	if(!pos)
		return 0;
	return SmartFindSum(Width, pos);
}
int LetsPlay(unsigned short xmax, unsigned short ymax)
{
 
	unsigned short curx, cury, cursx, curlsy, currsy, pos;
	int sumfinded = 0, i, k;
	unsigned short TempBestSum[MAXWIDTH +3];
	while(FindNextPlace(xmax, ymax, &curx, &cury, &cursx, &curlsy, &currsy))
	{
		sumfinded = 0;
		ZeroBestSum();
		sumfinded = FindRectangle(curlsy, cursx);
		if(!sumfinded)
		{
			sumfinded = FindRectangle(currsy, cursx);
		}
/*	
		if(!sumfinded)
		{
			k = FindArray(curlsy, Rectangles[0][0].count);
			if(k && Rectangles[k][0].count && Rectangles[k][1].width <= cursx)
			{
				BestSum[0] = cursx - Rectangles[k][1].width;
				BestSum[1] = 1;
				BestSum[2] = curlsy;
				BestSum[3] = Rectangles[k][1].width;
				sumfinded = 1;
			}
 
			k = FindArray(currsy, Rectangles[0][0].count);
			if(k && Rectangles[k][0].count && Rectangles[k][1].width <= cursx)
			{
				if(!sumfinded || BestSum[3] > Rectangles[k][1].width)
				{
					BestSum[0] = cursx - Rectangles[k][1].width;
					BestSum[1] = 1;
					BestSum[2] = currsy;
					BestSum[3] = Rectangles[k][1].width;
					sumfinded = 1;
				}
			}
		}
 
*/
		for(k = 3;!sumfinded && k>1;k--)
		{
			ZeroBestSum();
			FindRectangle(curlsy, cursx/k);
			if(BestSum[1] > 0)
			{
				sumfinded = 1;
			}
			if(!sumfinded)
			{
				FindRectangle(currsy, cursx/k);
				if(BestSum[1] > 0)
					sumfinded = 1;
			}
			if(sumfinded)
			{
				BestSum[0] += cursx-cursx/k;
			}
		}
 
		memcpy(TempBestSum, BestSum, (BestSum[1]+3)*sizeof(unsigned short));
 
		if(!sumfinded)
		{
			ZeroBestSum();
			if(Rectangles[0][0].count < 1)
				return 1;
			for(pos = Rectangles[0][0].count;pos>0;pos--)
			{
				if(Rectangles[pos][0].width > ymax-cury)
					continue;
				sumfinded = SmartFindSum(cursx, pos);
				if(sumfinded)
					break;
			}
			if(TempBestSum[1] && !sumfinded)
				memcpy(BestSum, TempBestSum, (TempBestSum[1]+3)*sizeof(unsigned short));
		}
		if(BestSum[1] > 0)
			sumfinded = 1;
 
		if(!sumfinded)
		{
			FillSquare(curx, cury, cursx, curlsy, 1);
		}else
		{
			for(i =0; i<BestSum[1];i++)
			{
				cursx = BestSum[i+3];
 
				if(BestSum[0] != 0 && BestSum[2] > curlsy)
				{
					FillSquare((unsigned short)(curx + BestSum[0]), cury, cursx, BestSum[2], 0);
				}
				else
				{
					FillSquare(curx, cury, cursx, BestSum[2], 0);
				}
				nUsedElements++;
 
				DeleteItem(cursx, BestSum[2]);
				curx += cursx;
				
			}
		}
	}
	return 1;
}
 
int PrintSquare(int xmax, int ymax)
{
	unsigned short i,j;
	printf("%u\n", nUsedElements);
	for(i = 0;i<xmax;i++)
	{
		for(j = 0;j<ymax;j++)
		{
			if(Square[i][j]!=(unsigned int)-1 && Square[i][j]!=0)
			{
				printf("%u %u %u %u\n", i+1, j+1, i + (Square[i][j]>>16), j + (Square[i][j]&0xffff));
				FillSquare(i, j, (unsigned short)(Square[i][j]>>16), (unsigned short)(Square[i][j]&0xffff),1);
			}
		}
	}
	return 1;
	
}
void GenRandom(int maxc, int maxw)
{
	int i, w, h, c;
	for(i=0;i<maxc;i++)
	{
		w = 1+(rand()*(maxw-1))/RAND_MAX;
		h = 1+(rand()*(maxw-1))/RAND_MAX;
		c = 2;
		AddRectangle(w, h, c);
		printf("%d %d %d\n", w, h, c);
	}
}
void ReadData(int * pmax)
{
	int i, n, x,y,c, max;
 
	scanf("%d %d", &max, &n);
	Prepare(max);
	for(i =0;i<n;i++)
	{
		scanf("%d %d %d", &x, &y, &c);
		if(x<=0 || y<=0 || x > max || y > max)
			continue;
		AddRectangle(x, y, c);
	}
//	GenRandom((rand()*1000)/RAND_MAX, 10);
	SortRectangles();
 
	nCountRect = Rectangles[0][0].count;
 
	*pmax = max;
}
 
 
 
int main()
{
	int i, n, max;
 
	srand(time(NULL));
	scanf("%d", &n);
	for(i = 0;i<n;i++)
	{
		ReadData(&max);
//		if(max > 800)
//		{
//			printf("0\n");
//			continue;
//		}
		if(!LetsPlay(max, max))
			return 1;
		if(!PrintSquare(max, max))
			return 1;
	}
 
	return 0;
}