oj.uz

답안 #382198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382198 2021-03-26T17:04:05 Z mohamedsobhi777 Cutting a rectangle (LMIO18_staciakampis) C++14
0 / 100
 1000 ms 1900 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 28 ms 364 KB Output is correct
4 Correct 47 ms 364 KB Output is correct
5 Incorrect 1 ms 372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Execution timed out 1085 ms 1900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 28 ms 364 KB Output is correct
4 Correct 47 ms 364 KB Output is correct
5 Incorrect 1 ms 372 KB Output isn't correct
6 Halted 0 ms 0 KB -