# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
991225 | 2024-06-01T15:27:54 Z | model_code | Cutting a Rectangle (BOI24_rectangle) | C++17 | 57 ms | 13428 KB |
#include <vector> #include <map> #include <algorithm> #include <cstdio> using namespace std; int N, i, j, c; long long S, w, h, x, 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) { x = w; w = h; h = x; } if (i < j) return; while (j >= 0 && u[j]) j--; } int main() { scanf ("%d", &N); S = 0; for (i = 0; i < N; i++) { scanf ("%d%d", &w, &h); a.push_back(w); b.push_back(h); S += w * h; l[h].push_back(i); l[w].push_back(i); u.push_back(false); } for (auto it0 = l.begin(); it0 != l.end(); ++it0) { h0 = it0->first; if (S % h0) continue; if (find(g.begin(), g.end(), min(S/h0, h0)) != g.end()) continue; h = h0; w = S / h; if (w < h) { x = w; w = h; h = x; } fill(u.begin(), u.end(), false); c = 0; j = N - 1; ok = true; while (c < N && ok) { ok = false; if (j >= 0) { if (a[j] > w) break; if (a[j] == w) { h -= b[j]; cut(j); continue; } } if (l.find(h) != l.end()) { auto &ll = l[h]; for (auto it = ll.begin(); it != ll.end(); it++) { if (u[*it] || b[*it] != h) continue; w -= a[*it]; cut(*it); } if (ok) continue; auto it = ll.begin(); if (u[*it] || a[*it] != h) continue; w -= b[*it]; cut(*it); } } if (c == N) g.push_back(min(S/h0, h0)); } sort(g.begin(), g.end()); printf("%d\n", g.size()); for (i = 0; i < g.size(); i++) printf("%d\n", g[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 36 ms | 13212 KB | Output is correct |
4 | Correct | 38 ms | 13244 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 41 ms | 12976 KB | Output is correct |
7 | Correct | 43 ms | 13112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 36 ms | 13212 KB | Output is correct |
14 | Correct | 38 ms | 13244 KB | Output is correct |
15 | Correct | 0 ms | 344 KB | Output is correct |
16 | Correct | 41 ms | 12976 KB | Output is correct |
17 | Correct | 43 ms | 13112 KB | Output is correct |
18 | Correct | 39 ms | 13380 KB | Output is correct |
19 | Correct | 54 ms | 13380 KB | Output is correct |
20 | Correct | 57 ms | 13284 KB | Output is correct |
21 | Correct | 11 ms | 2904 KB | Output is correct |
22 | Correct | 50 ms | 13164 KB | Output is correct |
23 | Correct | 45 ms | 13428 KB | Output is correct |
24 | Correct | 1 ms | 604 KB | Output is correct |
25 | Correct | 37 ms | 13380 KB | Output is correct |