Submission #1139860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139860		tmm	Cutting a rectangle (LMIO18_staciakampis)	C++20	0 / 100	0 ms	324 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(){
    fin >> n;
    r.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        fin >> 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(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;
        }
    }
    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 || already_added[min(Arie / r[i].a, 1LL * 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));
            already_added[min(1LL * r[i].a, Arie / r[i].a)] = 1;
        }

        if(r[i].b < b || Arie % r[i].b || already_added[min(Arie / r[i].b, 1LL * r[i].b)]) continue;
        add_missing();
        if(canBeSeparated(min(1LL * r[i].b, Arie / r[i].b), max(1LL * r[i].b, Arie / r[i].b))) {
            sol.push_back(min(1LL * r[i].b, Arie / r[i].b));
            already_added[min(Arie / r[i].b, 1LL * r[i].b)] = 1;
        }
    }
    fout << sol.size() << '\n';
    sort(sol.begin(), sol.end());
    for(auto x: sol){
        fout << x << "\n";
    }
}

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