AOJ 1149: Cut the Cake
問題
Cut the Cake | Aizu Online Judge
- 大きさwxdのケーキをn回切り分ける
- 入力はp, sという形で与えられ、p番目のピースの左上から時計回りにs進んだところを起点に垂直に切断する
- ピースの番号はカットが終わるたびに出来たのが古い順、出来たのが同じなら小さい順に振られる
- 面積が小さい順に各ピースの面積を表示
方針
コード
#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回目)