oj.uz

답안 #477378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477378 2021-10-01T19:57:03 Z BThero Cutting a rectangle (LMIO18_staciakampis) C++17
100 / 100
 116 ms 122640 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);
				}

				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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 117596 KB Output is correct
2 Correct 67 ms 117584 KB Output is correct
3 Correct 72 ms 117616 KB Output is correct
4 Correct 72 ms 117680 KB Output is correct
5 Correct 73 ms 117700 KB Output is correct
6 Correct 68 ms 117656 KB Output is correct
7 Correct 63 ms 117700 KB Output is correct
8 Correct 67 ms 117684 KB Output is correct
9 Correct 69 ms 117676 KB Output is correct
10 Correct 65 ms 117608 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 117684 KB Output is correct
2 Correct 69 ms 117676 KB Output is correct
3 Correct 65 ms 117608 KB Output is correct
4 Correct 92 ms 122424 KB Output is correct
5 Correct 87 ms 122376 KB Output is correct
6 Correct 87 ms 122300 KB Output is correct
7 Correct 96 ms 122312 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 117596 KB Output is correct
2 Correct 67 ms 117584 KB Output is correct
3 Correct 72 ms 117616 KB Output is correct
4 Correct 72 ms 117680 KB Output is correct
5 Correct 73 ms 117700 KB Output is correct
6 Correct 68 ms 117656 KB Output is correct
7 Correct 63 ms 117700 KB Output is correct
8 Correct 67 ms 117684 KB Output is correct
9 Correct 69 ms 117676 KB Output is correct
10 Correct 65 ms 117608 KB Output is correct
11 Correct 92 ms 122424 KB Output is correct
12 Correct 87 ms 122376 KB Output is correct
13 Correct 87 ms 122300 KB Output is correct
14 Correct 96 ms 122312 KB Output is correct
15 Correct 91 ms 122516 KB Output is correct
16 Correct 96 ms 122516 KB Output is correct
17 Correct 101 ms 122420 KB Output is correct
18 Correct 72 ms 118652 KB Output is correct
19 Correct 94 ms 122348 KB Output is correct
20 Correct 116 ms 122640 KB Output is correct
21 Correct 78 ms 117752 KB Output is correct
22 Correct 105 ms 122340 KB Output is correct