Problem 0536 : Shuffle
問題概要
日本語なので本文参照。
(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0536)
解法
連続する順序で並んでいるカードの区間を[a,b]として表現する。
区間を一つのカードとして並べ替えなどの操作する。
シャッフルするときにカードはいくつかの区間に分割される。
(分割の操作は下のコードではsplit関数で行っている)
線形リストを使わない手抜き解法で効率悪い気がするんだけどAOJが爆速なので通った。
ソースコード
typedef vector<pair<int,int> > vp; void split(vp &v,int x){ int cnt=0,l,r; fr(i,v){ l=i->first; r=i->second; if(x<=cnt+r-l+1){ if(x==cnt+r-l+1)break; i=v.erase(i); v.insert(i,mp(l+x-cnt,r)); v.insert(i,mp(l,l+x-cnt-1)); break; } cnt+=r-l+1; } } void cut(vp &v,int x,int y){ split(v,x); split(v,y); vp ret; int l,r,cnt=0; rep(i,v.size()){ cnt+=v[i].second-v[i].first+1; if(cnt==x)l=i; if(cnt==y)r=i; } for(int i=r+1;i<v.size();i++)ret.pb(v[i]); for(int i=l+1;i<=r;i++)ret.pb(v[i]); for(int i=0;i<=l;i++)ret.pb(v[i]); v=ret; } int main() { int n,m,p,q,r; while(scanf("%d",&n),n){ vp taba; taba.pb(mp(1,n)); scanf("%d",&m); scanf("%d%d%d",&p,&q,&r); rep(i,m){ int x,y; scanf("%d%d",&x,&y); cut(taba,x,y); } if(p>1)split(taba,p-1); if(q<n)split(taba,q); int ans=0,cnt=0,a,b; bool plus=0; fr(i,taba){ a=i->first; b=i->second; if(cnt+1==p)plus=1; if(plus){ if(b<=r)ans+=b-a+1; else if(a<=r)ans+=r-a+1; } cnt+=b-a+1; if(cnt==q)break; } printf("%d\n",ans); } return 0; }