제출 #1265604

#제출 시각아이디문제언어결과실행 시간메모리
1265604herominhsteveCutting a Rectangle (BOI24_rectangle)C++20
100 / 100
59 ms13384 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...