Volume 5 / 0536

情報オリンピック 2008予選 解答

Problem 0536 : Shuffle / シャッフル

安直に配列を使ってシミュレーションしようとすると、配列が確保できなくなってRuntime Errorが出る。カードの数10^9とかだもの。
で、情報オリンピックのサイトの解説見ても実装の仕方がパッと思いつかない……。とりあえず保留。

// 安直な解き方（完全ではない）
#include <iostream>
#include <vector>

using namespace std;



vector<int> shuffle( vector<int> src, int x, int y )
{
	int i;
	vector<int> result;

	result.clear();
	result.push_back(0);

	// C
	for( i=y+1; i<src.size(); i++ )
		result.push_back(src[i]);

	// B
	for( i=x+1; i<=y; i++ )
		result.push_back(src[i]);

	// A
	for( i=1; i<=x; i++ )
		result.push_back(src[i]);

	return result;
}

int main(void)
{
	int n, m, p, q, r, x, y;
	int i, cnt;
	vector<int> cards;

	while( cin >> n, n!=0 ){
		cards.resize(n+1);

		cin >> m;
		cin >> p >> q >> r;

		for( i=1; i<=n; i++ )
			cards[i] = i;

		for( i=0; i<m; i++ ){
			cin >> x >> y;
			cards = shuffle( cards, x, y );
		}

		cnt = 0;
		for( i=p; i<=q; i++ )
			if( cards[i] <= r )
				cnt++;

		cout << cnt << endl;
	}

	return 0;
}