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

,

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

## solution

$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;
}