AizOJ 0301 Baton Relay Game（模拟）

Baton Relay Game
Time Limit : 1 sec, Memory Limit : 131072 KB
Japanese
バトンリレーゲーム
アカベ高校では、毎年全校生徒が参加するゲームを行っています。まず、校庭に N 人の全校生徒が円形に並びます。図のように、各生徒は 0 から N-1 までの番号が書かれたゼッケンを付けています。

ゲームではバトンを１本使い、最初はゼッケン 0 番の生徒がバトンを持っています。そこから、以下の手順を M 回繰り返します。まず、現時点でバトンを持っている生徒が適当な正の整数 a を宣言します。a が偶数のときは時計回り、奇数のときは反時計回りに隣の生徒にバトンを渡していき、a 番目にバトンを受け取った生徒が脱落します。脱落した生徒は、時計回りで隣の生徒にバトンを渡し、円から抜けます。

ゲームが終わった後に円に残った生徒は、放課後の掃除が１年間免除されます。しかし、ここ数年は生徒数が増えたため、全校生徒を集めるのが難しくなってきています。そこで、競技プログラミング部のあなたは、シミュレーションで掃除が免除される生徒を求めるプログラムを作成するよう頼まれました。

指定した生徒が掃除を免除されているかどうかを質問したとき、それに答えるプログラムを作成してください。

入力
入力は以下の形式で与えられる。

N M Q
a1 a2 … aM
q1 q2 … qQ
入力は３行であり、１行目に生徒の人数 N (10 ≤ N ≤ 200000)、繰り返し回数 M (5 ≤ M < N)、生徒が掃除を免除されるかどうかを問い合わせる質問の個数 Q (1 ≤ Q ≤ 1000) が与えられる。続く１行に、i 回目の繰り返しで最初にバトンを持っている生徒が宣言する整数ai (1 ≤ ai ≤ 100) が与えられる。続く１行に、質問としてゼッケン番号 qi (0 ≤ q < N) が与えられる。

出力
質問ごとに、ゼッケン番号 qi の生徒が掃除を免除されるかどうかを i 行目に出力する。掃除が免除されるなら 1 を、されないなら 0 を出力する。

入出力例

入力例
10 5 3
2 6 5 18 3
3 0 5
出力例
1
0
1
题目大意：n个人围成圈做游戏……
题目链接: https://onlinejudge.u-aizu.ac.jp/problems/0301
solution：用L、R数组分别保存每个数左边右边的数、如此模拟

#include <bits/stdc++.h>
using namespace std;

int v[210000], L[210000], R[210000];
//利用L,R数组记录某个点的左右关系

int main()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	for (int i = 0; i < a; ++i)
	{
		v[i] = 1;
        L[i] = (i + a - 1) % a;
        R[i] = (i + 1) % a;
	}
	int now = 0, d;
	for (int i = 0; i < b; ++i){
		scanf("%d", &d);
		if (d % 2){
			//找到当前个人左边的第d个人
			for (int j = 0; j < d; ++j)now = L[now];
			v[now] = 0;
			int l = L[now], r = R[now];
			R[l] = r;
			L[r] = l;
			now = r;
		}else{
			//找到当前个人左边的第d个人
			for (int j = 0; j < d; ++j)now = R[now];
			v[now] = 0;
			int l = L[now], r = R[now];
			R[l] = r;
			L[r] = l;
			now = r;
		}
		
	}
	for (int i = 0; i < c; ++i){
		int d;
		scanf("%d", &d);
		printf("%d\n", v[d]);
	}
	return 0;
}