AOJ 1149: ケーキカット / Cut the Cake

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149

何か便利そうなやつという認識があったのでstd::minmaxを使ってみたのだが、参照を返す性質上tieと合わせるとバグになるようだった。

solution

指示されたように実装する。$O(N^2)$でよい。

$s$は周期性と結果をsortすることから、$s \bmod (H + W)$だけ考えればよい。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

pair<pair<int, int>, pair<int, int> > split(int h, int w, int s) {
    s %= h + w;
    if (0 < s and s < w) {
        int w1 = s;
        int w2 = w - w1;
        tie(w1, w2) = minmax({ w1, w2 });
        return { { h, w1 }, { h, w2 } };
    } else if (w < s) {
        int h1 = s - w;
        int h2 = h - h1;
        tie(h1, h2) = minmax({ h1, h2 });
        return { { h1, w }, { h2, w } };
    } else {
        assert (false);
    }
}

int main() {
    while (true) {
        int n, initial_w, initial_h; scanf("%d%d%d", &n, &initial_w, &initial_h);
        if (n == 0 and initial_w == 0 and initial_h == 0) break;
        vector<pair<int, int> > piece;
        piece.emplace_back(initial_h, initial_w);
        while (n --) {
            int i, s; scanf("%d%d", &i, &s); -- i;
            int h, w; tie(h, w) = piece[i];
            piece.erase(piece.begin() + i);
            pair<int, int> p1, p2; tie(p1, p2) = split(h, w, s);
            piece.push_back(p1);
            piece.push_back(p2);
        }
        vector<int> area;
        for (auto piece_i : piece) {
            int h, w; tie(h, w) = piece_i;
            area.push_back(h * w);
        }
        whole(sort, area);
        repeat (i, area.size()) {
            printf("%d%c", area[i], i + 1 == area.size() ? '\n' : ' ');
        }
    }
    return 0;
}