oj.uz

Submission #477375

# Submission time Handle Problem Language Result Execution time Memory
477375 2021-10-01T19:51:48 Z BThero Cutting a rectangle (LMIO18_staciakampis) C++17
45 / 100
 1000 ms 123888 KB 
#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);
				}

				changed = 0;

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

							if (a[idx].first == w) {
								h -= a[idx].second;
							}
							else {
								h -= a[idx].first;
							}
						}
					}
				}

				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 * d <= sum; d++) {
			if (sum % d == 0) {
				if (check(d, sum / d)) T.insert(d);
			}
		}
	}

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

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

	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117716 KB Output is correct
2 Correct 54 ms 117632 KB Output is correct
3 Correct 81 ms 117588 KB Output is correct
4 Correct 103 ms 117608 KB Output is correct
5 Correct 64 ms 117624 KB Output is correct
6 Correct 105 ms 117708 KB Output is correct
7 Correct 55 ms 117700 KB Output is correct
8 Correct 61 ms 117700 KB Output is correct
9 Correct 61 ms 117700 KB Output is correct
10 Correct 59 ms 117624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117700 KB Output is correct
2 Correct 61 ms 117700 KB Output is correct
3 Correct 59 ms 117624 KB Output is correct
4 Correct 80 ms 122400 KB Output is correct
5 Correct 89 ms 122540 KB Output is correct
6 Correct 92 ms 122332 KB Output is correct
7 Correct 87 ms 122260 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117716 KB Output is correct
2 Correct 54 ms 117632 KB Output is correct
3 Correct 81 ms 117588 KB Output is correct
4 Correct 103 ms 117608 KB Output is correct
5 Correct 64 ms 117624 KB Output is correct
6 Correct 105 ms 117708 KB Output is correct
7 Correct 55 ms 117700 KB Output is correct
8 Correct 61 ms 117700 KB Output is correct
9 Correct 61 ms 117700 KB Output is correct
10 Correct 59 ms 117624 KB Output is correct
11 Correct 80 ms 122400 KB Output is correct
12 Correct 89 ms 122540 KB Output is correct
13 Correct 92 ms 122332 KB Output is correct
14 Correct 87 ms 122260 KB Output is correct
15 Correct 149 ms 123408 KB Output is correct
16 Correct 105 ms 123368 KB Output is correct
17 Correct 139 ms 123184 KB Output is correct
18 Correct 82 ms 118736 KB Output is correct
19 Correct 106 ms 123200 KB Output is correct
20 Correct 154 ms 123616 KB Output is correct
21 Correct 57 ms 117856 KB Output is correct
22 Execution timed out 1087 ms 123888 KB Time limit exceeded