Submission #1166375

#TimeUsernameProblemLanguageResultExecution timeMemory
1166375tamyteCutting a rectangle (LMIO18_staciakampis)C++20
100 / 100
162 ms21548 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; set<pair<int, int>> A, B; ll tot = 0; set<ll> vis; bool check(ll x, ll y) { // cout << x << " " << y << endl; if (x < y) swap(x, y); if (y == 0) return true; auto p = *prev(A.end()); auto q = *prev(B.end()); // cout << "P: " << p.first << " " << p.second << " ? " << x << endl; // cout << "Q: " << q.first << " " << q.second << " ? " << y << endl; if (p.first > x || q.first > y) return false; bool res = false; if (p.first == x) { A.erase(p); B.erase({p.second, p.first}); // cout << "in\n"; res = check(x, y - p.second); // cout << "out\n"; A.insert(p); B.insert({p.second, p.first}); return res; } if (q.first == y) { B.erase(q); A.erase({q.second, q.first}); res = check(x - q.second, y); B.insert(q); A.insert({q.second, q.first}); return res; } auto it = A.lower_bound({y, -1}); if (it != A.end()) { p = *it; // cout << "P:" << p.first << " " << p.second << "\n"; if (p.first == y) { A.erase(p); B.erase({p.second, p.first}); // cout << "in\n"; res = check(x - p.second, y); // cout << "out\n"; A.insert(p); B.insert({p.second, p.first}); return res; } } return res; } bool good(ll x) { if (tot % x) return false; x = min(x, tot / x); if (vis.count(x)) return false; vis.insert(x); return check(x, tot / x); } int main() { int n; cin >> n; vector<int> a(n), b(n); for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; tot += 1LL * a[i] * b[i]; A.insert({a[i], b[i]}); B.insert({b[i], a[i]}); } set<ll> p; for (int i = 0; i < n; ++i) { if (good(b[i])) { p.insert(b[i]); } if (good(a[i])) { p.insert(min((ll)a[i], tot / a[i])); } // cout << endl; } cout << p.size() << endl; for (auto& u : p) { cout << u << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...