AOJ 1149 ケーキカット (ICPC 国内予選 2007 C) (300 点)

AOJ-ICPC 300 点。

問題へのリンク

問題概要

(略) ケーキをカットして行ってできるピースの面積をそれぞれ答えよ

考えたこと

ケーキの中がどう分割されているかは一切関係ないので、毎回バラバラなピースがあってそこから 1 個選んで分割してそれを最後尾に付け加えるような実装でよさそうなん。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pint; // (w, d)
bool cmp(pint a, pint b) { return a.first * a.second < b.first * b.second; }

int main() {
  int N, W, D;
  while (cin >> N >> W >> D, W) {
    vector<pint> res; res.push_back(pint(W, D));
    for (int xxx = 0; xxx < N; ++xxx) {
      int p, s; cin >> p >> s; --p;
      pint cur = res[p]; res.erase(res.begin() + p);
      pint ne[2];
      for (int i = 0; i < 2; ++i) ne[i].first = cur.first, ne[i].second = cur.second;
      s %= (cur.first + cur.second) * 2;
      if (s <= cur.first) ne[0].first = s, ne[1].first = cur.first - ne[0].first;
      else if (s - cur.first <= cur.second) ne[0].second = s-cur.first, ne[1].second = cur.second - ne[0].second;
      else if (s-cur.first-cur.second <= cur.first) ne[0].first = cur.first - (s-cur.first-cur.second), ne[1].first = cur.first - ne[0].first;
      else ne[0].second = (cur.first+cur.second)*2 - s, ne[1].second = cur.second - ne[0].second;
      if (ne[0] < ne[1]) res.push_back(ne[0]), res.push_back(ne[1]);
      else res.push_back(ne[1]), res.push_back(ne[0]);
    }
    sort(res.begin(), res.end(), cmp);
    for (int i = 0; i < res.size(); ++i) {
      cout << res[i].first * res[i].second;
      if (i != (int)res.size()-1) cout << " ";
    } 
    cout << endl;
  }
}