Submission #1139774

#TimeUsernameProblemLanguageResultExecution timeMemory
1139774stanraresCutting a rectangle (LMIO18_staciakampis)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int> > rectangles;
set<pair<int, int> > s;

int main() {
    int k;
    cin >> k;

    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        rectangles.emplace_back(a, b);
    }

    for (auto &rect: rectangles) {
        s.insert(rect);
    }

    bool changes = true;
    while (changes) {
        changes = false;
        auto it = s.begin();
        while (it != prev(s.end())) {
            auto next_it = next(it);

            int a1 = it->first, b1 = it->second;
            int a2 = next_it->first, b2 = next_it->second;

            if (a1 == a2) {
                int new_a1 = a1, new_b1 = b1 + b2;
                s.erase(it);
                s.erase(next_it);
                s.insert({new_a1, new_b1});
                changes = true;
            } else if (a1 == b2 && b1 != a2) {
                int new_a1 = a1, new_b1 = a2 + b1;
                s.erase(it);
                s.erase(next_it);
                s.insert({new_a1, new_b1});
                changes = true;
            } else if (a1 == b2 && b1 == a2) {
                int new_a1 = a1, new_b1 = a2 + b1;
                int new_a2 = b1, new_b2 = a1 + b2;
                s.erase(it);
                s.erase(next_it);
                s.insert({new_a1, new_b1});
                s.insert({new_a2, new_b2});
                changes = true;
            }
            it = s.lower_bound(*next_it);
        }
    }

    cout << s.size() << endl;
    for (auto &rect: s) {
        cout << min(rect.first, rect.second) << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...