Submission #1139783

#TimeUsernameProblemLanguageResultExecution timeMemory
1139783tmmCutting a rectangle (LMIO18_staciakampis)C++20
0 / 100
0 ms328 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>

using namespace std;
struct rectangles{
    int a;
    int b;
    int used;
};

int n;
vector<rectangles> r;
typedef long long mare;
mare Arie;
int b = -1;
vector<int> sol;

unordered_map<int,set<int>> fr;

void reading(){
    cin >> n;
    r.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> r[i].a >> r[i].b;
        Arie += 1LL * r[i].a * r[i].b;
        b = max(b, r[i].b);
    }
}
bool canBeSeparated(int l, int L){
    while(l * L == 0){
        if(!fr[l].empty()) {
            int ind = *(fr[l].rbegin());
            fr[l].erase(ind);
            if(r[ind].a != r[ind].b)
                fr[(r[ind].a == l ? r[ind].b : r[ind].a)].erase(ind);
            r[ind].used = 0;
            if(r[ind].a == l)
                L -= r[ind].b;
            else
                L -= r[ind].a;
        }else{
            if(fr[L].empty()) return 0;

            int ind = *(fr[L].rbegin());
            fr[L].erase(ind);
            if(r[ind].a != r[ind].b)
                fr[(r[ind].a == L ? r[ind].b : r[ind].a)].erase(ind);
            r[ind].used = 0;
            if(r[ind].a == L)
                l -= r[ind].b;
            else
                l -= r[ind].a;
        }
    }
    return 1;
}
void add_missing(){
    for(int i = 1; i <= n; i++){
        if(r[i].used == 0){
            fr[r[i].a].insert(i);
            if(r[i].b != r[i].a) fr[r[i].b].insert(i);
            r[i].used = 1;
        }
    }
}
int main() {
    reading();
    for(int i = 1; i <= n; i++){
        if(r[i].a < b || Arie % r[i].a) continue;
        add_missing();
        if(canBeSeparated(min(1LL * r[i].a, Arie / r[i].a), max(1LL * r[i].a, Arie / r[i].a)))
            sol.push_back(min(1LL * r[i].a, Arie / r[i].a));

    }
    cout << sol.size() << '\n';
    for(auto x: sol){
        cout << x << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...