Назад к лучшим решениям Status: AC, problem ZRIS, contest ZEL06. By natalia (Natalia Bondarenko), 2006-03-02 13:19:00.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define all(x) x.begin(), x.end()
 
#define NMAX 1003
#define KMAX 100005
#define INF 1000006
#define limit 45000
 
#define IN_FILE "input.txt"
#define OUT_FILE "output.txt"
 
int n, k;
 
struct TRect
{
	int w, h, l;	
} r[KMAX];
 
 
bool Comp(const TRect &a, const TRect &b)
{
	return (a.w * a.h > b.w * b.h || (a.w * a.h == b.w * b.h && (a.w > b.w || (a.w == b.w && (a.h > b.h)))));
}
 
bool Comp2(const TRect &a, const TRect &b)
{
	return (a.w > b.w || (a.w == b.w && (a.h > b.h)));
}
 
int a[NMAX][2*NMAX];
 
struct TAns
{
	int x1, y1, x2, y2, num;
};
 
vector <TAns> ans, v;
int ans_s;
 
inline void FillBlock1(int lx, int ly, int rx, int ry)
{
	for(int i = lx; i < rx; i++)
	{
		a[i][ly << 1] = ry;
		a[i][(ry << 1) - 1] = 1;
	}
}
inline void FillBlock0(int lx, int ly, int rx, int ry)
{
	for(int i = lx; i < rx; i++)
	{
		a[i][ly << 1] = 0;
		a[i][(ry << 1) - 1] = 0;
	}
}
 
int t;
 
void Rec(int x, int y, int l, int s, int max_free)
{
	++t;
	if (ans_s == 0)
	{
		return;
	}
	if (s < ans_s)
	{
		ans_s = s;
		ans.resize(v.size());
		copy(all(v), ans.begin());
	}
 
	if (t > limit)
	{
		return;
	}
	if (max_free == y)
	{
		max_free = -1;
	}
	if (y >= n)
	{
		y = 0;
		++x;
	}
	while (x < n && a[x][y << 1] > 0)
	{
		y = a[x][y << 1];
		if (y >= n)
		{
			++x; y = 0;
		}
	}
 
	while (l < k && (r[l].h * r[l].w > s || r[l].l == 0))
	{
		++l;
	}
	if (x >= n || l >= k)
	{
		return;
	}
 
	if (max_free == -1)
	{
		max_free = y;
		while (max_free < n && a[x][max_free << 1] == 0)
		{
			++max_free;
		}
	}
 
	TAns q;
	q.x1 = x+1; q.y1 = y+1;
 
	for(int i = l; i < k; i++)
	{
		if (r[i].l > 0 && x + r[i].h <= n && y + r[i].w <= max_free)
		{
			q.x2 = x + r[i].h; q.y2 = y + r[i].w;
			q.num = i;
			v.push_back(q);
			--r[i].l;
			FillBlock1(x, y, x + r[i].h, y + r[i].w);
			Rec(x, y + r[i].w, l, s - r[i].h * r[i].w, max_free);
			if (t > limit)
			{
				return;
			}
			FillBlock0(x, y, x + r[i].h, y + r[i].w);
			++r[i].l;
			v.pop_back();
		}
		if (r[i].w != r[i].h && r[i].l > 0 && x + r[i].w <= n && y + r[i].h <= max_free)
		{
			q.x2 = x + r[i].w; q.y2 = y + r[i].h;
			q.num = i;
			v.push_back(q);
			--r[i].l;
			FillBlock1(x, y, x + r[i].w, y + r[i].h);
			Rec(x, y + r[i].h, l, s - r[i].w * r[i].h, max_free);
			if (t > limit)
			{
				return;
			} 
			FillBlock0(x, y, x + r[i].w, y + r[i].h);
			++r[i].l;
			v.pop_back();
		}
	}
}
 
struct TColon
{
	int h, w, l, r;
};
 
TColon col, next;
 
int main()
{
	int test; scanf("%d", &test);
	forn(run, test)
	{
		scanf("%d %d", &n, &k);	
		forn(i, k)
		{
			scanf("%d %d %d", &r[i].w, &r[i].h, &r[i].l);
			if (r[i].w < r[i].h)
			{
				swap(r[i].w, r[i].h);
			}
		}
 
		if (n <= 200)
		{
			sort(r, r + k, Comp);
	
			v.clear();
			ans.clear(); ans_s = INF;
			forn(i, n)
			{
				forn(j, 2*n)
				{
					a[i][j] = 0;
				}
			}
			t = 0;
			Rec(0, 0, 0, n*n, n);
		}
		else
		{
			ans.clear();
			sort(r, r + k, Comp2);
 
			col.h = n;
			col.w = n;
			col.l = 0;
			col.r = 0;
			while (true)
			{
				if (col.w == 0)
				{
					break;
				}
				bool flag = false;
				forn(i, k)
				{
					if (r[i].l > 0 && r[i].w <= col.w && r[i].h <= col.h)
					{
						TAns q;
						q.x1 = col.l+1;
						q.y1 = col.r+1;
						q.x2 = col.l + r[i].w;
						q.y2 = col.r + r[i].h;
						--r[i].l;
						ans.push_back(q);
						col.r = q.y2;
						col.h -= r[i].h;
						if (!flag)
						{
							flag = true;
							next.l = q.x2;
							next.r = 0;
							next.h = n;
							next.w = n - q.x2;
						}
						if (col.h == 0)
						{
							break;
						}
					}
				}
				if (!flag)
				{
					break;
				}
				col = next;
			}
			
		}
		printf("%d\n", ans.size());
		forn(i, ans.size())
		{
			printf("%d %d %d %d\n", ans[i].x1, ans[i].y1, ans[i].x2, ans[i].y2);
		}
	}
 
	return 0;
}