AOJ 1149 PKU 3327 Cut the Cakes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149&lang=jp
http://poj.org/problem?id=3327
シミュレーションする問題。
超絶めんどくさい問題だと思って放置していたやつ。
nの数が小さいから愚直にできるのでそんなでも無かったです。
vector<PI> pea; main(){ int n,w,d; while(cin>>n>>w>>d,w){ pea.clear(); pea.pb(mp(w,d)); rep(i,n){ int p,s; cin>>p>>s; --p; PI tp=pea[p]; for(int i=p;i<SZ(pea)-1;i++)pea[i]=pea[i+1]; pea.pop_back(); s%=(tp.F+tp.S)*2; PI t1,t2; if(s<tp.F){ t1=mp(tp.F-s,tp.S); t2=mp(s,tp.S); }else if(s<tp.F+tp.S){ t1=mp(tp.F,tp.S+tp.F-s); t2=mp(tp.F,s-tp.F); }else if(s<tp.F*2+tp.S){ t1=mp(tp.F*2+tp.S-s,tp.S); t2=mp(s-tp.S-tp.F,tp.S); }else{ t1=mp(tp.F,tp.F*2+tp.S*2-s); t2=mp(tp.F,s-tp.F*2-tp.S); } if(t1.F*t1.S>t2.F*t2.S)swap(t1,t2); pea.pb(t1),pea.pb(t2); } vector<int> ans; rep(i,SZ(pea))ans.pb(pea[i].F*pea[i].S); sort(ALL(ans)); rep(i,SZ(ans)){ if(i)cout<<' '; cout<<ans[i]; } cout<<endl; } }