AOJ 0536 Shuffle
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0536
解法
やるだけ問題なんだけど実装キツい
カードの数字なんて気にしなくてよいので、最初に、r以下のカードを白い碁石、rよりおおきいカードを黒い碁石にでも置き換えると、ちょっと実装が楽になる。
#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; int N; vector<P> s(int x, int y, vector<P> c){ vector<P> ret; queue<P> A, B; int n = 0; int i = 0; P next; for(; n < x; i++){ if(n + c[i].second <= x){ A.push(c[i]); n += c[i].second; if(n == x){ next = c[i+1]; i += 2; break; } }else{ A.push(P(c[i].first, x - n)); next = P(c[i].first, c[i].second - x + n); i++; n = x; break; } } //printf("next = (%d %d)\n", next.first, next.second); if(n + next.second <= y){ n += next.second; B.push(next); if(n == y){ next = c[i]; i++; } }else{ B.push(P(next.first, y - n)); next = P(next.first, next.second - y + n); n = y; } for(; n < y; i++){ if(n + c[i].second <= y){ B.push(c[i]); n += c[i].second; if(n == y){ next = c[i+1]; i += 2; break; } }else{ B.push(P(c[i].first, y - n)); next = P(c[i].first, c[i].second - y + n); i++; n = y; break; } } //printf("next = (%d %d)\n", next.first, next.second); ret.push_back(next); for(; i < c.size(); i++) ret.push_back(c[i]); while(!B.empty()){ ret.push_back(B.front()); B.pop(); } while(!A.empty()){ ret.push_back(A.front()); A.pop(); } return ret; } int cnt(int p, int q, vector<P> c){ int n = 0; int i = 0; int ans = 0; for(;n < p;i++){ if(c[i].first == 0 && p <= n + c[i].second){ ans += c[i].second + n - p + 1; } n += c[i].second; } for(; n < q; i++){ if(c[i].first == 0){ if(q <= n + c[i].second){ ans += q - n; }else{ ans += c[i].second; } } n += c[i].second; } return ans; } int main(){ int p, q, r, m; while(scanf("%d", &N) && N != 0){ vector<P> card; scanf("%d", &m); scanf("%d %d %d", &p, &q, &r); card.push_back(P(0, r)); card.push_back(P(1, N-r)); for(int i = 0; i < m; i++){ int x, y; scanf("%d %d", &x, &y); card = s(x, y, card); } printf("%d\n", cnt(p, q, card)); } return 0; }