Submission #1173653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173653		xnqs	Cutting a Rectangle (BOI24_rectangle)	C++20	0 / 100	0 ms	324 KiB

Main

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

int cuts;
std::vector<std::pair<int,int>> arr;

bool can_solve(int64_t a, int64_t b, int pos = 0) {
	//std::cout << a << " " << b << " " << pos << "\n";
	if (pos == cuts-1) {
		return (a == arr[pos].first && b == arr[pos].second);
	}

	bool ret = 0;
	if (arr[pos].first == a && b - arr[pos].second > 0) {
		int64_t new_a = std::max(a, b - arr[pos].second);
		int64_t new_b = std::min(a, b - arr[pos].second);
		ret |= can_solve(new_a, new_b, pos+1);
	}
	if (!ret && arr[pos].second == b && a - arr[pos].first > 0) {
		int64_t new_a = std::max(b, a - arr[pos].first);
		int64_t new_b = std::min(b, a - arr[pos].first);
		ret |= can_solve(new_a, new_b, pos+1);
	}

	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> cuts;
	int64_t tot_area = 0;
	for (int i = 0, a, b; i < cuts; i++) {
		std::cin >> a >> b;
		arr.emplace_back(a,b);
		tot_area += 1LL*a*b;
	}

	std::reverse(arr.begin(), arr.end());

	std::vector<int64_t> ret;
	if (tot_area % arr[0].first == 0 && can_solve(std::max(tot_area/arr[0].first, (int64_t)arr[0].first), std::min(tot_area/arr[0].first, (int64_t)arr[0].first))) {
		ret.emplace_back(std::min(tot_area/arr[0].first, (int64_t)arr[0].first));
	}
	if (tot_area % arr[0].second == 0 && can_solve(std::max(tot_area/arr[0].second, (int64_t)arr[0].second), std::min(tot_area/arr[0].second, (int64_t)arr[0].second))) {
		ret.emplace_back(std::min(tot_area/arr[0].second, (int64_t)arr[0].second));
	}
	/*for (int64_t d = 1; d*d <= tot_area; d++) {
		if (tot_area%d==0) {
			if (can_solve(tot_area/d, d)) {
				ret.emplace_back(d);
			}
		}
	}*/

	std::sort(ret.begin(), ret.end());
	ret.erase(std::unique(ret.begin(), ret.end()), ret.end());

	std::cout << ret.size() << "\n";
	for (const auto& i : ret) {
		std::cout << i << "\n";
	}
}

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