Submission #198168

#	Time	Username	Problem	Language	Result	Execution time	Memory
198168		model_code	Cutting a rectangle (LMIO18_staciakampis)	C++14	100 / 100	129 ms	13536 KiB

staciakampis

#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

int K, i, j, c;
long long S, w, h, x, h0;
vector<long long> a, b, g;
vector<bool> u;
map<long long, vector<int> > l;
bool ok;

void cut(int i) {
  c++;
  u[i] = true;
  ok = true;
  if (w < h) {
    x = w;
    w = h;
    h = x;
  }
  if (i < j)
    return;
  while (j >= 0 && u[j])
    j--;
}

int main() {
  scanf("%d", &K);
  S = 0;
  for (i = 0; i < K; i++) {
    scanf("%d%d", &w, &h);
    a.push_back(w);
    b.push_back(h);
    S += w * h;
    l[h].push_back(i);
    l[w].push_back(i);
    u.push_back(false);
  }
  for (auto it0 = l.begin(); it0 != l.end(); ++it0) {
    h0 = it0->first;
    if (S % h0)
      continue;
    if (find(g.begin(), g.end(), min(S / h0, h0)) != g.end())
      continue;
    h = h0;
    w = S / h;
    if (w < h) {
      x = w;
      w = h;
      h = x;
    }
    fill(u.begin(), u.end(), false);
    c = 0;
    j = K - 1;
    ok = true;
    while (c < K && ok) {
      ok = false;
      if (j >= 0) {
        if (a[j] > w)
          break;
        if (a[j] == w) {
          h -= b[j];
          cut(j);
          continue;
        }
      }
      if (l.find(h) != l.end()) {
        auto& ll = l[h];
        for (auto it = ll.begin(); it != ll.end(); it++) {
          if (u[*it] || b[*it] != h)
            continue;
          w -= a[*it];
          cut(*it);
        }
        if (ok)
          continue;
        auto it = ll.begin();
        if (u[*it] || a[*it] != h)
          continue;
        w -= b[*it];
        cut(*it);
      }
    }
    if (c == K)
      g.push_back(min(S / h0, h0));
  }
  sort(g.begin(), g.end());
  printf("%d\n", g.size());
  for (i = 0; i < g.size(); i++)
    printf("%d\n", g[i]);
}

Compilation message (stderr)

staciakampis.cpp: In function 'int main()':
staciakampis.cpp:33:25: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d%d", &w, &h);
                   ~~    ^
staciakampis.cpp:33:25: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
staciakampis.cpp:90:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<long long int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", g.size());
                  ~~~~~~~~^
staciakampis.cpp:91:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < g.size(); i++)
               ~~^~~~~~~~~~
staciakampis.cpp:92:24: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' [-Wformat=]
     printf("%d\n", g[i]);
                        ^
staciakampis.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &K);
   ~~~~~^~~~~~~~~~
staciakampis.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &w, &h);
     ~~~~~^~~~~~~~~~~~~~~~

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