제출 #1112905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112905		gelastropod	Cutting a Rectangle (BOI24_rectangle)	C++14	100 / 100	240 ms	29732 KiB

Main

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define int long long

signed main(signed argc, char *argv[])
{
	int K, w, h, A = 0;
	cin >> K;
	vector<pair<int, int>> dims;
	map<int, int> ws;
	map<int, vector<int>> hs;
	set<int> sides;
	vector<int> ans;
	for (int i = 0; i < K; i++)
	{
		cin >> w >> h;
		dims.push_back({w, h});
		ws[w] = i + 1;
		hs[h].push_back(i);
		sides.insert(w);
		sides.insert(h);
		A += w * h;
	}
	vector<bool> used(K, false);
	map<int, int> hu;
	for (int i : sides)
	{
		used = vector<bool>(K, false);
		if (A % i != 0)
			continue;
		int j = A / i;
		if (i < j)
			swap(i, j);
		if (binary_search(ans.begin(), ans.end(), j))
			continue;
		int crntw = i, crnth = j;
		int numrect = 0;
		auto chu = hu;
		while (numrect < K)
		{
			if (crntw < crnth)
				swap(crntw, crnth);
			if (ws[crntw] != 0 && !used[ws[crntw] - 1])
			{
				crnth -= dims[ws[crntw] - 1].second;
				numrect++;
				used[ws[crntw] - 1] = true;
				continue;
			}
			if (chu[crnth] == 0)
			{
				for (int i : hs[crnth])
				{
					if (!used[i])
					{
						crntw -= dims[i].first;
						numrect++;
						used[i] = true;
					}
				}
				chu[crnth] = 1;
				continue;
			}
			if (ws[crnth] != 0 && !used[ws[crnth] - 1])
			{
				crntw -= dims[ws[crnth] - 1].second;
				numrect++;
				used[ws[crnth] - 1] = true;
				continue;
			}
			break;
		}
		if (numrect == K)
			ans.push_back(j);
	}
	cout << ans.size() << '\n';
	for (int i : ans)
		cout << i << '\n';
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 55 / 55