#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
int N, c, j;
long long S, w, h, h0;
vector<long long> a, b, g;
vector<bool> u;
map<long long, vector<int>> l;
bool ok;
void cut(int i) {
c++;
u[i] = true;
ok = true;
if (w < h) swap(w, h);
if (i < j) return;
while (j >= 0 and u[j]) j--;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
S = 0;
a.resize(N);
b.resize(N);
u.assign(N, false);
for (int i = 0; i < N; i++) {
cin >> w >> h;
a[i] = w;
b[i] = h;
S += w * h;
l[h].push_back(i);
l[w].push_back(i);
}
for (auto &p : l) {
h0 = p.first;
if (S % h0) continue;
long long candidate = min(S / h0, h0);
h = h0;
w = S / h;
if (w < h) swap(w, h);
fill(allof(u), false);
c = 0;
j = N - 1;
ok = true;
while (c < N and ok) {
ok = false;
if (j >= 0) {
if (a[j] > w) break;
if (a[j] == w) {
h -= b[j];
cut(j);
continue;
}
}
if (l.count(h)) {
auto &ll2 = l[h];
for (int idx : ll2) {
if (u[idx] || b[idx] != h) continue;
w -= a[idx];
cut(idx);
}
if (ok) continue;
int idx = ll2[0];
if (u[idx] || a[idx] != h) continue;
w -= b[idx];
cut(idx);
}
}
if (c == N) g.push_back(candidate);
}
sort(allof(g));
g.erase(unique(allof(g)), g.end());
cout << g.size() << el;
for (long long val : g) cout << val << el;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |