Submission #364828

#	Time	Username	Problem	Language	Result	Execution time	Memory
364828		_martynas	Cutting a rectangle (LMIO18_staciakampis)	C++11	25 / 100	1091 ms	39568 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>;

int k;

ll TotalArea = 0;
set<ll> CheckedLengths;
set<ll> AvailableLengths;
map<ll, multiset<ll, greater<ll>>> AllByLength;
map<ll, multiset<ll, greater<ll>>> ByLength;
vector<pll> Rectangles;

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

    CheckedLengths.insert(min(w,h));
    //cerr << "TEST: " << w << " " << h << endl;
    ByLength = AllByLength;

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

    cerr << "Copy ended: " << duration << "ms\n";
    */

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

    bool changed = true;
    while(changed)
    {
        //DEBUG(w);
        //DEBUG(h);
        changed = false;
        if(h > w)
        {
            swap(w, h);
        }
        if(ByLength.count(w))
        {
            changed = true;
            multiset<ll> Erase;
            for(ll x : ByLength[w])
            {
                Erase.insert(x);
                h -= x;
            }
            auto pointerByLengthW = &ByLength[w];
            for(ll x : Erase)
            {
                if(x != w)
                {
                    ByLength[x].erase(ByLength[x].find(w));
                    pointerByLengthW->erase(pointerByLengthW->find(x));
                }
                else
                {
                    ByLength[x].erase(ByLength[x].find(w));
                }
                if(!ByLength[x].size())
                {
                    ByLength.erase(x);
                }
            }
            ByLength[w].clear();
            ByLength.erase(w);
        }
        else if(ByLength.count(h))
        {
            changed = true;
            multiset<ll> Erase; // rikiuoti pagal ilgi, nes jei reikia trinti, tai trinti ilgiausia
            for(ll x : ByLength[h])
            {
                Erase.insert(x);
                w -= x;
                if(ByLength.begin()->first <= w || w < h) /// Patikrinti ar reikia nutraukti, kai w < h, ir gali buti per letai
                {
                    break;
                }
            }
            for(ll x : Erase)
            {
                if(x != h)
                {
                    ByLength[h].erase(ByLength[h].find(x));
                    ByLength[x].erase(ByLength[x].find(h));
                }
                else
                {
                    ByLength[h].erase(ByLength[h].find(x));
                }
                if(!ByLength[x].size())
                {
                    ByLength.erase(x);
                }
            }
            if(!ByLength[h].size()) // pirmas else if ciklas perejo visus elementus
            {
                ByLength.erase(h);
            }
        }
    }
    //cerr << "-----------------------\n";

    /*
    t2 = high_resolution_clock::now();

    duration = duration_cast<milliseconds>( t2 - t1 ).count();

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


    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++)
    {
        if(Rectangles[i].F != Rectangles[i].S)
        {
            AllByLength[Rectangles[i].F].insert(Rectangles[i].S);
            AllByLength[Rectangles[i].S].insert(Rectangles[i].F);
        }
        else
        {
            AllByLength[Rectangles[i].F].insert(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)) && !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 && !AvailableLengths.count(min(TotalArea / a, a)) && !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:182: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=]
  182 |     printf("%d\n", AvailableLengths.size());
      |             ~^     ~~~~~~~~~~~~~~~~~~~~~~~
      |              |                          |
      |              int                        std::set<long long int>::size_type {aka long unsigned int}
      |             %ld
staciakampis.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
staciakampis.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  144 |         scanf("%lld%lld", &Rectangles[i].F, &Rectangles[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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