Submission #991225

#	Time	Username	Problem	Language	Result	Execution time	Memory
991225		model_code	Cutting a Rectangle (BOI24_rectangle)	C++17	100 / 100	57 ms	13428 KiB

Main

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

int N, 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", &N);
    S = 0;
    for (i = 0; i < N; 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 = N - 1;
        ok = true;
        while (c < N && 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 == N)
            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)

Main.cpp: In function 'int main()':
Main.cpp:29:18: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   29 |         scanf ("%d%d", &w, &h);
      |                 ~^     ~~
      |                  |     |
      |                  int*  long long int*
      |                 %lld
Main.cpp:29:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   29 |         scanf ("%d%d", &w, &h);
      |                   ~^       ~~
      |                    |       |
      |                    int*    long long int*
      |                   %lld
Main.cpp:76:14: 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=]
   76 |     printf("%d\n", g.size());
      |             ~^     ~~~~~~~~
      |              |           |
      |              int         std::vector<long long int>::size_type {aka long unsigned int}
      |             %ld
Main.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (i = 0; i < g.size(); i++)
      |                 ~~^~~~~~~~~~
Main.cpp:78:18: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wformat=]
   78 |         printf("%d\n", g[i]);
      |                 ~^
      |                  |
      |                  int
      |                 %lld
Main.cpp:26:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf ("%d", &N);
      |     ~~~~~~^~~~~~~~~~
Main.cpp:29:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf ("%d%d", &w, &h);
      |         ~~~~~~^~~~~~~~~~~~~~~~

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