oj.uz

Submission #366003

# Submission time Handle Problem Language Result Execution time Memory
366003 2021-02-12T17:38:02 Z _martynas Cutting a rectangle (LMIO18_staciakampis) C++11
45 / 100
 108 ms 14308 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 vi = vector<int>;

const int MAX_N = 1e5+5;

int k;

ll TotalArea = 0;
set<ll> CheckedLengths;
set<ll> AvailableLengths;
map<int, vi> 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--;
        }

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 76 ms 14052 KB Output is correct
5 Correct 80 ms 14180 KB Output is correct
6 Correct 74 ms 13924 KB Output is correct
7 Correct 74 ms 13924 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 76 ms 14052 KB Output is correct
12 Correct 80 ms 14180 KB Output is correct
13 Correct 74 ms 13924 KB Output is correct
14 Correct 74 ms 13924 KB Output is correct
15 Correct 79 ms 14180 KB Output is correct
16 Correct 90 ms 14308 KB Output is correct
17 Correct 108 ms 14180 KB Output is correct
18 Runtime error 26 ms 5980 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -