oj.uz

Submission #366011

# Submission time Handle Problem Language Result Execution time Memory
366011 2021-02-12T17:57:40 Z _martynas Cutting a rectangle (LMIO18_staciakampis) C++11
100 / 100
 131 ms 15212 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory 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 Correct 83 ms 13664 KB Output is correct
5 Correct 84 ms 13664 KB Output is correct
6 Correct 84 ms 13408 KB Output is correct
7 Correct 82 ms 13408 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 83 ms 13664 KB Output is correct
12 Correct 84 ms 13664 KB Output is correct
13 Correct 84 ms 13408 KB Output is correct
14 Correct 82 ms 13408 KB Output is correct
15 Correct 87 ms 13664 KB Output is correct
16 Correct 107 ms 13664 KB Output is correct
17 Correct 131 ms 13684 KB Output is correct
18 Correct 24 ms 3048 KB Output is correct
19 Correct 109 ms 14560 KB Output is correct
20 Correct 87 ms 15212 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 67 ms 15200 KB Output is correct