3957285_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> T;
vector <T> v[4], q[4];

bool cmp(T a, T b)
{
	return a.first < b.first;
}

int main()
{
	int w[4], h[4];
	int W, H, d[4];
	int i, hh, cas = 1;

	while (true)
	{
		scanf("%d%d", &W, &H);
		if (W == 0 && H == 0)
		{
			break;
		}
		for (i = 0; i < 4; i++)
		{
			d[i] = i;
			v[i].clear();
			q[i].clear();
			scanf("%d%d", &w[i], &h[i]);
			for (hh = 1; hh <= H; hh++)
			{
				if (w[i] * hh % h[i] == 0 && w[i] * hh / h[i] <= W)
				{
					v[i].push_back(make_pair(w[i] * hh / h[i], hh));
					q[i].push_back(make_pair(hh, w[i] * hh / h[i]));
				}
			}
			sort(v[i].begin(), v[i].end(), cmp);
			sort(q[i].begin(), q[i].end(), cmp);
		}
		int yes = 0;
		do
		{
			for (i = 0; !yes && i < v[d[0]].size(); i++)
			{
				int min, max, mid;
				int ans0 = -1;
				int ans1 = -1;
				int ans2 = -1;
				int ans3 = -1;
				min = 0;max = v[d[1]].size() - 1;
				while (min <= max)
				{
					mid = (min + max) >> 1;
					if (v[d[1]][mid].first < W - v[d[0]][i].first)
					{
						min = mid + 1;
					}
					else
					{
						if (v[d[1]][mid].first > W - v[d[0]][i].first)
						{
							max = mid - 1;
						}
						else
						{
							ans1 = mid;
							break;
						}
					}
				}
				if (ans1 == -1)
					continue;
				min = 0;max = v[d[2]].size() - 1;
				while (min <= max)
				{
					mid = (min + max) >> 1;
					if (q[d[2]][mid].first < H - v[d[0]][i].second)
					{
						min = mid + 1;
					}
					else
					{
						if (q[d[2]][mid].first > H - v[d[0]][i].second)
						{
							max = mid - 1;
						}
						else
						{
							ans2 = mid;
							break;
						}
					}
				}
				if (ans2 == -1)
					continue;
				if (v[d[1]][ans1].second != v[d[0]][i].second && q[d[2]][ans2].second != v[d[0]][i].first)
					continue;
				int tw = W - q[d[2]][ans2].second;
				int th = H - v[d[1]][ans1].second;
				min = 0;max = v[d[3]].size() - 1;
				while (min <= max)
				{
					mid = (min + max) >> 1;
					if (v[d[3]][mid].first < tw)
						min = mid + 1;
					else
					{
						if (v[d[3]][mid].first > tw)
							max = mid - 1;
						else
						{
							ans0 = mid;
							break;
						}
					}
				}
				if (ans0 == -1 || v[d[3]][ans0].second != th)
					continue;
				yes = 1;
			}
		}while(!yes && next_permutation(d, d + 4));
		printf("Set %d: %s\n", cas++, yes?"Yes":"No");
	}
	return 0;
}