Submission #364703

#	Time	Username	Problem	Language	Result	Execution time	Memory
364703		_martynas	Cutting a rectangle (LMIO18_staciakampis)	C++11	0 / 100	1092 ms	20716 KiB

staciakampis

#include <bits/stdc++.h>

using namespace std;

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

using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;

int k;

ll TotalArea = 0;
set<ll> AvailableLengths;
map<int, set<int>> ByLength;
vector<pii> Rectangles;

bool test(ll w, ll h)
{
    //cerr << "TEST: " << w << " " << h << endl;
    for(int i = 0; i < k; i++)
    {
        ByLength[Rectangles[i].F].insert(Rectangles[i].S);
        ByLength[Rectangles[i].S].insert(Rectangles[i].F);
    }
    bool changed = true;
    while(changed)
    {
        //DEBUG(w);
        //DEBUG(h);
        changed = false;
        if(h > w)
        {
            swap(w, h);
        }
        if(ByLength.count(w))
        {
            changed = true;
            for(auto x : ByLength[w])
            {
                ByLength[x].erase(w);
                h -= x;
            }
            ByLength[w].clear();
            ByLength.erase(w);
        }
        else if(ByLength.count(h))
        {
            changed = true;
            for(auto x : ByLength[h])
            {
                ByLength[x].erase(h);
                w -= x;
            }
            ByLength[h].clear();
            ByLength.erase(h);
        }
    }
    return w == 0 || h == 0;
}

int main()
{
    scanf("%d", &k);
    Rectangles.resize(k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d%d", &Rectangles[i].F, &Rectangles[i].S);
        TotalArea += Rectangles[i].F * Rectangles[i].S;
    }

    for(int i = 0; i < k; i++)
    {
        ll a = Rectangles[i].F, b = Rectangles[i].S;
        // test a x b;
        if(TotalArea % b == 0 && !AvailableLengths.count(min(TotalArea / b, b)))
        {
            if(test(TotalArea / b, b))
            {
                AvailableLengths.insert(min(TotalArea / b, b));
            }
        }
        // test b x a;
        if(TotalArea % a == 0 && !AvailableLengths.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
3
2 1
3 2
4 2

2
2 2
4 2
*/

Compilation message (stderr)

staciakampis.cpp: In function 'int main()':
staciakampis.cpp:95: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=]
   95 |     printf("%d\n", AvailableLengths.size());
      |             ~^     ~~~~~~~~~~~~~~~~~~~~~~~
      |              |                          |
      |              int                        std::set<long long int>::size_type {aka long unsigned int}
      |             %ld
staciakampis.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
staciakampis.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%d%d", &Rectangles[i].F, &Rectangles[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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