# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198168 | 2020-01-25T02:01:38 Z | model_code | Cutting a rectangle (LMIO18_staciakampis) | C++14 | 129 ms | 13536 KB |
#include <algorithm> #include <cstdio> #include <map> #include <vector> using namespace std; int K, 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", &K); S = 0; for (i = 0; i < K; 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 = K - 1; ok = true; while (c < K && 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 == K) 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 | 9 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 91 ms | 13272 KB | Output is correct |
5 | Correct | 91 ms | 13224 KB | Output is correct |
6 | Correct | 90 ms | 13016 KB | Output is correct |
7 | Correct | 90 ms | 13024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Correct | 87 ms | 13412 KB | Output is correct |
12 | Correct | 115 ms | 13228 KB | Output is correct |
13 | Correct | 129 ms | 13404 KB | Output is correct |
14 | Correct | 22 ms | 2924 KB | Output is correct |
15 | Correct | 115 ms | 13276 KB | Output is correct |
16 | Correct | 102 ms | 13536 KB | Output is correct |
17 | Correct | 4 ms | 760 KB | Output is correct |
18 | Correct | 99 ms | 13412 KB | Output is correct |
19 | Correct | 91 ms | 13272 KB | Output is correct |
20 | Correct | 91 ms | 13224 KB | Output is correct |
21 | Correct | 90 ms | 13016 KB | Output is correct |
22 | Correct | 90 ms | 13024 KB | Output is correct |