https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0301?year=2014
前提知識
考察過程
1. 制約として、aが小さいのが気になる
2. Maを考えると10^5*10^2=10^7なので簡単な計算なら間に合いそう
3. 隣に渡していって、1つ削除ができる…
4. 双方向リストで実現できる
解法
https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0301/judge/3157915/C++14
双方向リストを作ろう。
L[i] := iの左側(反時計回り)の数
R[i] := iの右側(時計回り)の数
bat := 現在バトンを持っている人
これを修正しながらシミュレートしていく。
最後にバトンを持っている人がbat、左側の人がl、右側の人がrだとする。
すると、R[l] = r, L[r] = lとすると、batが消える。
次にバトンを持つのは右側なのでbat=rとなる。
このときに答えも更新しておこう。
ans[i] := i番目の人の掃除が免除されているか
int N, M, Q; int L[201010], R[201010]; int ans[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> Q; rep(i, 0, N) L[i] = i - 1, R[i] = i + 1; L[0] = N - 1; R[N - 1] = 0; rep(i, 0, N) ans[i] = 1; int bat = 0; rep(_, 0, M) { int a; cin >> a; if (a % 2 == 0) { rep(i, 0, a) bat = R[bat]; } else { rep(i, 0, a) bat = L[bat]; } ans[bat] = 0; int l = L[bat]; int r = R[bat]; R[l] = r; L[r] = l; bat = r; } rep(_, 0, Q) { int q; cin >> q; printf("%d\n", ans[q]); } }