Submission #1139884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139884		pmm	Cutting a rectangle (LMIO18_staciakampis)	C++20	100 / 100	118 ms	21528 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<mare> 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);
        r[i].used = 1;
    }
}

bool canBeSeparated(mare latime, mare lungime) {
    while(1LL * latime * lungime) {
        // prima data verific daca am vreun drept cu una dintre laturi = lungime
        if(!fr[lungime].empty()) {

            //stergere
            int ind = *( fr[lungime].rbegin() );
            fr[lungime].erase(ind);
            if(r[ind].a != r[ind].b)
                fr[(r[ind].a == lungime ? r[ind].b : r[ind].a)].erase(ind);
            r[ind].used = 1;

            //decupare
            if(r[ind].a == lungime)
                latime -= r[ind].b;
            else
                latime -= r[ind].a;

        } else {
            if(fr[latime].empty()) return 0; // daca nu gasesc nici latime atunci stop joc
            // am gasit drept cu uan dintre laturi = latime

            //stergere
            int ind = *( fr[latime].rbegin() );
            fr[latime].erase(ind);
            if(r[ind].a != r[ind].b)
                fr[(r[ind].a == latime ? r[ind].b : r[ind].a)].erase(ind);
            r[ind].used = 1;

            //decupare
            if(r[ind].a == latime)
                lungime -= r[ind].b;
            else
                lungime -= r[ind].a;
        }
        int newl = min(latime, lungime);
        int newL = max(latime, lungime);
        latime = newl;
        lungime = newL;
    }
    return 1;
}

void add_missing() {
    for(int i = 1; i <= n; i++) {
        if(r[i].used == 1) { //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 = 0;
        }
    }
}

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

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: 55 / 55