Submission #1265604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265604		herominhsteve	Cutting a Rectangle (BOI24_rectangle)	C++20	100 / 100	59 ms	13384 KiB

Main

#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;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 55 / 55