Submission #364709

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

staciakampis

#include <bits/stdc++.h>

using namespace std;

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

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

int k;

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

bool test(ll w, ll h)
{
    //cerr << "TEST: " << w << " " << h << endl;
    ByLength.clear();
    for(int i = 0; i < k; i++)
    {
        ByLength[Rectangles[i].F].insert(Rectangles[i].S);
        ByLength[Rectangles[i].S].insert(Rectangles[i].F);
    }

    /*
    for(auto it = ByLength.begin(); it != ByLength.end(); it++)
    {
        cerr << it->first << ":\n";
        for(int x : it->second)
        {
            cerr << x << " ";
        }
        cerr << endl;
    }
    */

    bool changed = true;
    while(changed)
    {
        changed = false;
        if(h > w)
        {
            swap(w, h);
        }
        if(ByLength.count(w))
        {
            changed = true;
            set<ll> Erase;
            for(ll x : ByLength[w])
            {
                Erase.insert(x);
                h -= x;
            }
            for(ll x : Erase)
            {
                ByLength[x].erase(w);
            }
            ByLength[w].clear();
            ByLength.erase(w);
        }
        else if(ByLength.count(h))
        {
            changed = true;
            set<ll> Erase;
            for(ll x : ByLength[h])
            {
                Erase.insert(x);
                w -= x;
            }
            for(ll x : Erase)
            {
                ByLength[x].erase(h);
            }
            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("%lld%lld", &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
10
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
*/

Compilation message (stderr)

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

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