Submission #1142691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142691		c32ardash	Cutting a rectangle (LMIO18_staciakampis)	C++20	45 / 100	120 ms	21228 KiB

staciakampis

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int KMAX=1e5+5;
bool viz[KMAX];
int a[KMAX], b[KMAX], k;
unordered_map<int, set<int>> fr;
set<ll> ans;
ll s;

ll get_other(ll x, ll y, ll z)
{
    return (x==y)?z:y;
}

bool check_all(ll lt, ll lu)
{
    while(lt*lu)
    {
        if(!fr[lu].empty())
        {
            int i=*fr[lu].rbegin();
            viz[i]=1; fr[a[i]].erase(i); fr[b[i]].erase(i);
            lt-=get_other(lu, a[i], b[i]);
        }
        else if(!fr[lt].empty())
        {
            int i=*fr[lt].rbegin();
            viz[i]=1; fr[a[i]].erase(i); fr[b[i]].erase(i);
            lu-=get_other(lt, a[i], b[i]);
        }
        else
            return 0;
        int nlt=min(lt, lu), nlu=max(lt, lu);
        lt=nlt; lu=nlu;
    }
    return 1;
}

void check_start(int x)
{
    if(s%x || ans.count(min(1LL*x, s/x)))
        return;
    for(int i=1;i<=k;i++)
        if(viz[i])
        {
            fr[a[i]].insert(i);
            fr[b[i]].insert(i);
            viz[i]=0;
        }
    if(check_all(min(1LL*x, s/x), max(1LL*x, s/x)))
        ans.insert(min(1LL*x, s/x));
}

int main()
{
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a[i]>>b[i];
        viz[i]=1;
        s+=1LL*a[i]*b[i];
    }
    for(int i=1;i<=k;i++)
    {
        check_start(a[i]);
        check_start(b[i]);
    }
    cout<<ans.size()<<'\n';
    for(auto x:ans)
        cout<<x<<'\n';
    return 0;
}

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