Submission #1139430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139430		teo_55	Cutting a rectangle (LMIO18_staciakampis)	C++20	25 / 100	1095 ms	3948 KiB

staciakampis

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define int long long
struct dr{
    int w, h;
};
std::vector<dr>v;
std::vector<dr>input;
std::vector<int>sol;
std::map<std::pair<int, int>, bool>f;
int n;
void back(dr current)
{
    if(v.empty())
    {
        int max=std::max(current.h, current.w);
        int min=std::min(current.h, current.w);
        if(!f[{min, max}])
        {
            f[{min, max}]=true;
            sol.push_back(min);
        }
        return;
    }
    for(int i=0; i<v.size(); ++i)
    {
        dr elim=v[i];
        if(v[i].w==current.h)
        {
            current.w+=v[i].h;
            v.erase(v.begin()+i);
            back(current);
            v.insert(v.begin()+i, elim);
            current.w-=v[i].h;
        }
        if(v[i].w==current.w)
        {
            current.h+=v[i].h;
            v.erase(v.begin()+i);
            back(current);
            v.insert(v.begin()+i, elim);
            current.h-=v[i].h;
        }

        if(v[i].h==current.h)
        {
            current.w+=v[i].w;
            v.erase(v.begin()+i);
            back(current);
            v.insert(v.begin()+i, elim);
            current.w-=v[i].w;
        }
        if(v[i].h==current.w)
        {
            current.h+=v[i].w;
            v.erase(v.begin()+i);
            back(current);
            v.insert(v.begin()+i, elim);
            current.h-=v[i].w;
        }
    }
}
signed main()
{
    std::cin>>n;
    for(int i=0; i<n; ++i)
    {
        int w, h;
        std::cin>>w>>h;
        input.push_back({w, h});
        v.push_back({w, h});
    }
    for(int i=0; i<v.size(); ++i)
    {
        dr current=v[i];
        v.erase(v.begin()+i);
        back(current);
        v.insert(v.begin()+i, current);
    }

    std::sort(sol.begin(), sol.end());
    std::cout<<sol.size()<<'\n';
    for(int i : sol)
        std::cout<<i<<'\n';
    return 0;
}

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