Submission #382198

#	Time	Username	Problem	Language	Result	Execution time	Memory
382198		mohamedsobhi777	Cutting a rectangle (LMIO18_staciakampis)	C++14	0 / 100	1085 ms	1900 KiB

staciakampis

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;

int n;
vii a;
ll area;

bool ok(ll x)
{
       ll A = x, B = area / x;
       vector<bool> tak(n, 0);
       while (A && B)
       {
              bool flag = 1;
              for (int i = 0; i < n; ++i)
              {
                     if (tak[i])
                     {
                            continue;
                     }
                     if (a[i].f == A)
                     {
                            B -= a[i].s;
                            tak[i] = 1;
                     }
                     else if (a[i].s == A)
                     {
                            B -= a[i].f;
                            tak[i] = 1;
                     }
                     else if (a[i].f == B)
                     {
                            A -= a[i].s;
                            tak[i] = 1;
                     }
                     else if (a[i].s == B)
                     {
                            A -= a[i].f;
                            tak[i] = 1;
                     }
                     else
                     {
                            continue;
                     }
                     flag = 0;
                     break;
              }
              if (flag)
              {
                     return 0;
              }
       }
       return 1;
       assert(A + B == 0);
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;
       a.resize(n);
       for (int i = 0; i < n; ++i)
       {
              cin >> a[i].f >> a[i].s;
              area += 1ll * a[i].f * a[i].s;
       }
       vector<pair<ll, ll>> ans;
       for (int i = 1; 1ll * i * i <= area; ++i)
       {
              if (area % i == 0)
              {
                     if (ok(i))
                     {
                            ans.pb({i, area / i});
                            if (ans.back().f > ans.back().s)
                            {
                                   swap(ans.back().f, ans.back().s);
                            }
                     }
              }
       }
       sort(all(ans));

       ans.erase(unique(all(ans)), ans.end());
       cout << sz(ans) << "\n";
       for (auto u : ans)
              cout << u.f << "\n";

       return 0;
}

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