Submission #477378

#	Time	Username	Problem	Language	Result	Execution time	Memory
477378		BThero	Cutting a rectangle (LMIO18_staciakampis)	C++17	100 / 100	116 ms	122640 KiB

staciakampis

#include <bits/stdc++.h>

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

using namespace std;

typedef long long ll;

vector<vector<int>> who(5e6 + 5);
set<vector<pair<int, int>>> S;
set<int> T;

void go(vector<pair<int, int>> vec) {
	for (int i = 0; i < sz(vec); i++) {
		if (vec[i].first < vec[i].second) {
			swap(vec[i].first, vec[i].second);
		}
	}

	sort(all(vec));

	if (S.insert(vec).second == 0) {
		return;
	}

	if (sz(vec) == 1) {
		T.insert(vec[0].second);
		return;
	}

	for (int a = 0; a < sz(vec); a++) {
		if (a + 1 < sz(vec) && vec[a].first == vec[a + 1].first) {
			vector<pair<int, int>> new_vec = vec;
			new_vec.erase(new_vec.begin() + a);
			new_vec.erase(new_vec.begin() + a);
			new_vec.pb({vec[a].first, vec[a].second + vec[a + 1].second});
			go(new_vec);
		}

		for (int b = a + 1; b < sz(vec); b++) {
			if (vec[a].first == vec[b].second) {
				vector<pair<int, int>> new_vec = vec;
				new_vec.erase(new_vec.begin() + b);
				new_vec.erase(new_vec.begin() + a);
				new_vec.pb({vec[a].first, vec[a].second + vec[b].first});
				go(new_vec);
			}

			if (vec[a].second == vec[b].second) {
				vector<pair<int, int>> new_vec = vec;
				new_vec.erase(new_vec.begin() + b);
				new_vec.erase(new_vec.begin() + a);
				new_vec.pb({vec[a].first + vec[b].first, vec[a].second});
				go(new_vec);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	ll sum = 0;

	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		sum += a[i].first * 1ll * a[i].second;
		who[a[i].first].pb(i);
		who[a[i].second].pb(i);
	}

	if (n <= 10 && 0) {
		go(a);
	}
	else {
		auto check = [&](ll w, ll h) -> bool {
			vector<int> was(n, 0);
			int alive = n;
			bool changed = 1;

			while (alive && changed) {
				if (w < h) {
					swap(w, h);
				}

				if (0 < w && w < sz(who)) {
					for (int idx : who[w]) {
						if (!was[idx]) {
							was[idx] = 1;
							--alive;
							h -= a[idx].second;
						}
					}
				}

				changed = 0;

				if (0 < h && h < sz(who)) {
					for (int idx : who[h]) {
						if (!was[idx] && a[idx].second == h) {
							was[idx] = 1;
							--alive;
							changed = 1;
							w -= a[idx].first;
						}
					}
					
					if (!changed) {
						for (int idx : who[h]) {
							if (!was[idx] && a[idx].first == h) {
								was[idx] = 1;
								--alive;
								changed = 1;
								w -= a[idx].second;
							}
						}
					}
				}
			}

			return alive == 0;
		};
		
		for (ll d = 1; d < sz(who); d++) {
			if (!who[d].empty() && sum % d == 0 && check(d, sum / d)) {
				T.insert(min(d, sum / d));
			}
		}
	}

	cout << sz(T) << '\n';

	for (int x : T) {
		cout << x << '\n';
	}

	return 0;
}

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