Submission #1139880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139880		pmm	Cutting a rectangle (LMIO18_staciakampis)	C++20	45 / 100	141 ms	21432 KiB

staciakampis

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <unordered_map>
#include <set>
#include <string>

using namespace std;
const string file = "c";

ifstream fin(file + ".in");
ofstream fout(file + ".out");

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;
unordered_map<int, bool> already_added;

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(mare l, mare L) {
    while(1LL * l * L) {
        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;
        }
        int newl = min(l, L);
        int newL = max(l, L);
        l = newl;
        L = newL;
    }
    return 1;
}


void add_missing() {
    for(int i = 1; i <= n; i++) {
        if(r[i].used == 0) { //dc este utilizat
            fr[r[i].a].insert(i);
            if(r[i].b != r[i].a) fr[r[i].b].insert(i);
            r[i].used = 1;
        }
    }
}

void tryMargin(int l) {
    if( Arie % l || already_added[min(Arie / l, 1LL * l)]==1) return;
    add_missing();
    if(canBeSeparated(min(1LL * l, Arie / l), max(1LL * l, Arie / l))) {
        sol.push_back(min(1LL * l, Arie / l));
    }
    already_added[min(1LL * l, Arie / l)] = 1;
}

int main() {
    reading();
    for(int i = 1; i <= n; i++) {
        tryMargin(r[i].a);
        tryMargin(r[i].b);
    }

    cout << sol.size() << '\n';

    sort(sol.begin(), sol.end());

    for(auto x: sol) {
        cout << x << "\n";
    }
}

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