aoj0301:Baton Relay Game

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0301

解法

無駄なくシミュレートできれば、くらいの計算量になります。

どうやって無駄なくシミュレートするかという話ですが、双方向連結リストを使うといいと思います。

各ノードについて、次のノードと前のノードの番号を覚えておきます。

i番目のノードの次のノードをnext[i],前のノードをprev[i]とします。

初期状態では、next[i]=(i+1)%N,prev[i]=(i-1+N)%Nとしておきます。

i番目のノードを削除するときは、next[prev[i]]=next[i],prev[next[i]]=prev[i]とします。（辺をつなぎなおす感じ）

コード

#include<bits/stdc++.h>
using namespace std;
 
int prev[200000],next[200000];
bool ok[200000];
int N,M,Q;
 
 
int main(){
    cin>>N>>M>>Q;
 
    for(int i=0;i<N;i++){
        prev[i]=(i-1+N)%N;
        next[i]=(i+1)%N;
    }
 
    int cur=0;
    while(M--){
        int a;
        cin>>a;
 
        if(a&1)while(a--)cur=prev[cur];
 
        else while(a--)cur=next[cur];
 
        ok[cur]=true;
        next[prev[cur]]=next[cur];
        prev[next[cur]]=prev[cur];
 
        cur=next[cur];
    }
 
    while(Q--){
        int q;
        cin>>q;
        cout<<1-ok[q]<<endl;
    }
}