oj.uz

Submission #477361

# Submission time Handle Problem Language Result Execution time Memory
477361 2021-10-01T19:22:45 Z BThero Cutting a rectangle (LMIO18_staciakampis) C++17
25 / 100
 109 ms 2884 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;
 
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);
 
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
 
	if (n <= 10) {
		go(a);
		cout << sz(T) << '\n';
 
		for (int x : T) {
			cout << x << '\n';
		}
	}
	else {
		ll sum = 0;
		int mx = 0;
		
		for (int i = 0; i < n; i++) {
			sum += a[i].first;
			mx = max(mx, a[i].first);
		}
 
		for (ll d = 1; d * d <= sum; d++) {
			if (sum % d == 0) {
				if (d >= mx || sum / d >= mx) T.insert(d);
			}
		}
 
		cout << sz(T) << '\n';
 
		for (ll x : T) {
			cout << x << '\n';
		}
	}
 
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 109 ms 2884 KB Output is correct
9 Correct 28 ms 1180 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 2884 KB Output is correct
2 Correct 28 ms 1180 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 13 ms 1100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 109 ms 2884 KB Output is correct
9 Correct 28 ms 1180 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 13 ms 1100 KB Output isn't correct
12 Halted 0 ms 0 KB -