3327(AOJ 1149):Cut the Cake

keyword

シミュレーション　C++

概要

長方形のケーキを何度かに分けて切った。各ピースの面積を小さい順に出力する問題。
入力の渡され方がとても面倒くさいけど基本的には実装ゲー。毎回番号を振りなおすというよく分からないことをしているのでmultisetで何か違うよなーと思いながらコツコツと書いた。

int main(){
    int i, n, w, d, p, s, cnt;
    while(scanf("%d%d%d",&n,&w,&d)){
        if(!(n||w||d)) break;
        multiset< pair<pair<int, int>, pair<int, int> > > ps;
        ITER(ps) itr;
        ps.insert(MP(MP(-1,w*d),MP(w,d)));

        REP(i,n){
            scanf("%d%d",&p,&s);
            itr = ps.begin();
            advance(itr,p-1);
            pair< pair<int, int>, pair<int, int> > t = *itr;
            ps.erase(itr);
            s %= t.sc.fs + t.sc.sc;
            if(s < t.sc.fs){
                ps.insert(MP(MP(i,s*t.sc.sc),MP(s,t.sc.sc)));
                ps.insert(MP(MP(i,(t.sc.fs-s)*t.sc.sc), MP(t.sc.fs-s,t.sc.sc)));
            }
            else{
                s -= t.sc.fs;
                ps.insert(MP(MP(i,s*t.sc.fs),MP(t.sc.fs, s)));
                ps.insert(MP(MP(i,(t.sc.sc-s)*t.sc.fs), MP(t.sc.fs,t.sc.sc-s)));
            }
        }

        priority_queue<int, vector<int>, greater<int> > Q;
        EACH(ps,it){
            Q.push(it->fs.sc);
        }

        cnt = 0;
        while(!Q.empty()){
            printf("%d",Q.top());
            Q.pop();
            if(cnt++<n)printf(" ");
            else printf("\n");
        }
    }
    return 0;
}