Cut the Cakes

[問題] ACM/ICPC 国内予選2007: Problem C
[解説]
データ構造はvectorが妥当かと思います。
最初vectorの要素に１つのケーキがあります。
次に、これを取り出して、２つの新しいピースを作り、面積が小さい順にvectorに挿入します。
問題の定義から、vectorのインデックスがそのままピースの番号になります。
逐次
指定されたピースを取り出して、それから２つの新しいピースを作り、小さい順に挿入して、、、
を繰り返していきます。
最後に、面積でソートするのを忘れずに出力です。

カットする処理が多少ごちゃごちゃしてますが、数学のセンスがある人はもっとかっこ良く書けるでしょう

001 #include<iostream>
002 #include<vector>
003 #include<algorithm>
004 using namespace std;
005 
006 class Piece{
007     public:
008     int d, w, area;
009     Piece(){}
010     Piece( int d, int w ): d(d), w(w){ area = d*w; }
011     
012     bool operator < ( const Piece &p ) const{
013         return area < p.area;
014     }
015 };
016 
017 int n;
018 vector<Piece> P;
019 
020 void cut( int p, int s ){
021     Piece target = P[p]; P.erase( P.begin() + p );
022     Piece new1, new2;
023     int d = target.d;
024     int w = target.w;
025     int c1 = w;
026     int c2 = w + d;
027     int c3 = 2*w + d;
028     int c4 = 2*w + 2*d;
029     s = s % c4;
030     if ( 0 < s && s < c1 ){
031         new1 = Piece( d, s ); new2 = Piece( d, c1 - s );
032     } else if ( c2 < s && s < c3 ){
033         new1 = Piece( d, c3 - s ); new2 = Piece( d, s - c2 );
034     } else if ( c1 < s && s < c2 ){
035         new1 = Piece( s - c1, w ); new2 = Piece( c2 - s, w );
036     } else if ( c3 < s && s < c4 ){
037         new1 = Piece( s - c3, w ); new2 = Piece( c4 - s, w );
038     }
039     
040     if ( new1 < new2 ){ P.push_back( new1 ); P.push_back( new2 ); }
041     else { P.push_back( new2 ); P.push_back( new1 ); }
042 }
043 
044 void simulate(){
045     int p, s;
046     for ( int i = 0; i < n; i++ ){
047         cin >> p >> s;
048         cut( p - 1, s );
049     }
050     sort( P.begin(), P.end() );
051     for ( int i = 0; i < P.size(); i++ ){
052         if ( i ) cout << " ";
053         cout << P[i].area;
054     }
055     cout << endl;
056 }
057 
058 bool input(){
059     int w, d;
060     cin >> n >> w >> d;
061     if ( n == 0 && w == 0 && d == 0 ) return false;
062     P.clear();
063     P.push_back(Piece(d, w));
064     return true;
065 }
066 
067 main(){
068     while ( input() ) simulate();
069 }