JOI2007予選 問題4＠C++(-18)

カードの状態を配列に記憶して、操作ごとに全部のカードを動かすアルゴリズムでもできるけど、今回は操作を配列に記憶して、カードごとに全部の操作を行うイメージのアルゴリズムにしてみた。時間計算量は変わらないし、配列一個で済む分こちらの方がシンプルだと思う。(ただしカードの上限は200枚、操作の上限は1000回なので、メモリ的にはこの方が食うが、誤差の範囲。)

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc,char* argv[])
{
	int n,m;
	scanf("%d\n",&n);
	scanf("%d\n",&m);
	vector<int> procs(m);
	for(int i=0;i<m;i++) {
		scanf("%d\n",&procs[i]);
	}
	for(int i=0;i<n<<1;i++) {
		int a=i;
		for(vector<int>::reverse_iterator j=procs.rbegin();j!=procs.rend();j++) {
			if(*j) {
				a=(a+*j)%(n<<1);
			} else {
				a=(a>>1)+(a&1)*n;
			}
		}
		printf("%d\n",a+1);
	}
	return 0;
}