# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1267532 | ilovewaguri | Cutting a Rectangle (BOI24_rectangle) | C++20 | 44 ms | 11968 KiB |
#include<bits/stdc++.h>
using namespace std;
#define NAME "REGTANGLE"
#define nl '\n'
#define mset(x,val) memset(x,val,sizeof(x))
typedef long long ll;
const int MAXN = (int)5e6+5;
int w[MAXN], h[MAXN];
bool visited[MAXN];
vector<int> big[MAXN], small[MAXN];
int K;
ll area;
void ccps() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen(NAME".inp","r")) {
freopen(NAME".inp","r",stdin);
freopen(NAME".out","w",stdout);
}
}
bool check_pair(int a, int b) {
mset(visited,false);
while(true) {
bool ok = false;
if (a < b) swap(a,b);
if (a < MAXN) {
for (int idx : big[a]) {
if (!visited[idx]) {
visited[idx] = true;
b -= h[idx];
ok = true;
}
}
}
if (ok) continue;
if (b < MAXN) {
for (int idx : small[b]) {
if (!visited[idx]) {
visited[idx] = true;
a -= w[idx];
ok = true;
}
}
}
if (ok) continue;
if (b < MAXN) {
for (int idx : big[b]) {
if (!visited[idx]) {
visited[idx] = true;
a -= h[idx];
ok = true;
}
}
}
if (!ok) break;
}
return (a * b == 0);
}
signed main() {
ccps();
cin >> K;
area = 0;
for (int i = 1; i <= K; i++) {
cin >> w[i] >> h[i];
area += 1LL * w[i] * h[i];
big[w[i]].push_back(i);
small[h[i]].push_back(i);
}
vector<int> res;
for (ll len = 1; len * len <= area; len++) {
if (area % len == 0) {
ll a = len, b = area / len;
if (a <= b && check_pair(a,b)) res.push_back(a);
if (a != b && b <= a && check_pair(b,a)) res.push_back(b);
}
}
cout << (int)res.size() << nl;
for (int x : res) cout << x << nl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |