AOJ 1149: Cut the Cake

問題

Cut the Cake | Aizu Online Judge

  • 大きさwxdのケーキをn回切り分ける
  • 入力はp, sという形で与えられ、p番目のピースの左上から時計回りにs進んだところを起点に垂直に切断する
  • ピースの番号はカットが終わるたびに出来たのが古い順、出来たのが同じなら小さい順に振られる
  • 面積が小さい順に各ピースの面積を表示

方針

  • 上のルールに従った切断をそのまま書く
  • 番号を簡単に振るために<演算子オーバーロードする
  • 面積による比較関数を使って最後の並び替えもsort()だけで出来るようにする

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

class cake {
public:
    int b, w, d;
    cake(int birth, int width, int depth)
        : b(birth), w(width), d(depth) {}
    bool operator<(const cake& r) const {
        if(b != r.b) return b < r.b;
        else return w*d < r.w*r.d;
    }
};

bool compare_area(const cake& r, const cake& l) {
    return r.w*r.d < l.w*l.d;
}

int main(void){
    vector<cake> C;
    int n, w, d, p, s;
    while(cin >> n >> w >> d && w && d) {
        C.clear();
        C.push_back(cake(0, w, d));
        rep(i, n) {
            cin >> p >> s;
            p--;
            sort(C.begin(), C.end());
            s = s%(C[p].w+C[p].d);
            if(s < C[p].w) {
                C.push_back(cake(i+1, C[p].w-s, C[p].d));
                C[p] = cake(i+1, s, C[p].d);
            } else {
                s -= C[p].w;
                C.push_back(cake(i+1, C[p].w, C[p].d-s));
                C[p] = cake(i+1, C[p].w, s);
            }
        }
        sort(C.begin(), C.end(), compare_area);
        rep(i, n) cout << C[i].w*C[i].d << " ";
        cout << C[n].w*C[n].d << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1904076

反省

合ってるはずなのにずっとWAだったから、一度全消去してから書き直したら通った(2回目)