読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

aoj0301:Baton Relay Game

解法

無駄なくシミュレートできれば、{\displaystyle O(\sum^M_{i=1}{a_i})}くらいの計算量になります。


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


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


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;
    }
}