Submission #366011

#	Time	Username	Problem	Language	Result	Execution time	Memory
366011		_martynas	Cutting a rectangle (LMIO18_staciakampis)	C++11	100 / 100	131 ms	15212 KiB

staciakampis

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

#define F first
#define S second
#define PB push_back
#define DEBUG(x) cerr << #x << " = " << x << "\n";

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

const int MAX_N = 1e5+5;

int k;

ll TotalArea = 0;
set<ll> CheckedLengths;
set<ll> AvailableLengths;
map<int, vl> ByLength;
ll A[MAX_N], B[MAX_N];

bool test(ll w, ll h)
{
    //auto t1 = high_resolution_clock::now();

    if(h > w)
    {
        swap(w, h);
    }

    CheckedLengths.insert(h);

    vector<bool> checked(k, false);

    bool changed = true;
    int r = k-1;

    while(r >= 0 && changed)
    {
        if(h > w)
        {
            swap(w, h);
        }
        if(checked[r])
        {
            r--;
            continue;
        }
        changed = false;
        if(A[r] > w)
        {
            break;
        }
        if(A[r] == w)
        {
            changed = true;
            checked[r] = true;
            h -= B[r];
            r--;
        }

        if(ByLength.count(h))
        {
            for(int index : ByLength[h])
            {
                if(checked[index])
                    continue;
                if(B[index] == h)
                {
                    changed = true;
                    checked[index] = true;
                    w -= A[index];
                }
            }

            if (changed)
              continue;
            auto it = ByLength[h].begin();
            if (checked[*it] || A[*it] != h)
              continue;
            changed = true;
            checked[*it] = true;
            w -= B[*it];
        }
    }

    /*
    auto t2 = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>( t2 - t1 ).count();

    cout << "Test took: " << duration << "ms\n";
    */

    return w == 0 || h == 0;
}

int main()
{
    /*
    freopen("lmio_2018_3e2_staciakampis_vyr.in", "r", stdin);
    freopen("lmio_2018_3e2_staciakampis_vyr.out", "w", stdout);
    */

    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%lld%lld", &A[i], &B[i]);
        TotalArea += A[i] * B[i];
        ByLength[A[i]].push_back(i);
        ByLength[B[i]].push_back(i);
    }

    for(int i = 0; i < k; i++)
    {
        ll a = A[i], b = B[i];
        // test a x b;
        if(TotalArea % b == 0 && !CheckedLengths.count(min(TotalArea / b, b)))
        {
            if(test(TotalArea / b, b))
            {
                AvailableLengths.insert(min(TotalArea / b, b));
            }
        }
        // test b x a;
        if(TotalArea % a == 0 && !CheckedLengths.count(min(TotalArea / a, a)))
        {
            if(test(TotalArea / a, a))
            {
                AvailableLengths.insert(min(TotalArea / a, a));
            }
        }
    }

    printf("%d\n", AvailableLengths.size());
    for(ll x : AvailableLengths)
    {
        printf("%lld\n", x);
    }

    return 0;
}

/* INPUT
10
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1

4
1 1
2 1
3 1
6 2


3
2 1
3 2
4 2
*/

Compilation message (stderr)

staciakampis.cpp: In function 'int main()':
staciakampis.cpp:137:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  137 |     printf("%d\n", AvailableLengths.size());
      |             ~^     ~~~~~~~~~~~~~~~~~~~~~~~
      |              |                          |
      |              int                        std::set<long long int>::size_type {aka long unsigned int}
      |             %ld
staciakampis.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
staciakampis.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         scanf("%lld%lld", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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