# CFR 786 A. Berzerk ( DP, Game )

Problem - A - Codeforces

The first line of input contains a single integer n (2 ≤ n ≤ 7000) — number of objects in game.
The second line contains integer k1 followed by k1 distinct integers s1, 1, s1, 2, ..., s1, k1 — Rick's set.
The third line contains integer k2 followed by k2 distinct integers s2, 1, s2, 2, ..., s2, k2 — Morty's set
1 ≤ ki ≤ n - 1 and 1 ≤ si, 1, si, 2, ..., si, ki ≤ n - 1 for 1 ≤ i ≤ 2.

dp[ i ][ j ] : 怪獸當前在星球 i，先手為 j 時，是先手必勝 / 必敗。( 遊戲不會結束的情況先擱著方便思考 )

O( N^2 ) / O( N )

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

const int MAXN = 7000;

int N;
vector< int > S[ 2 ];
int dp[ MAXN ][ 2 ]; // where, who -> pending / lose / win : -1 / 0 / 1

signed main(){
ios::sync_with_stdio( 0 );
{ // input
cin >> N;
int K1; cin >> K1;
S[ 0 ] = vector< int >( K1 );
for( int i = 0; i < K1; ++i ){
cin >> S[ 0 ][ i ];
}
int K2; cin >> K2;
S[ 1 ] = vector< int >( K2 );
for( int i = 0; i < K2; ++i ){
cin >> S[ 1 ][ i ];
}
}
{
memset( dp, -1, sizeof( dp ) );
vector< int > cnt( N * 2 ); // 行き先が 1 の数
queue< pair< int, int > > lque; // 必ず負ける状態の中でまだ更新していない
lque.emplace( 0, 0 );
lque.emplace( 0, 1 );
while( not lque.empty() ){
queue< pair< int, int > > nlq; // next lque
while( not lque.empty() ){
int u, p;
tie( u, p ) = lque.front();
lque.pop();
dp[ u ][ p ] = 0;
for( int d : S[ p ^ 1 ] ){
int v = ( u - d + N ) % N;
if( dp[ v ][ p ^ 1 ] != -1 ) continue;
dp[ v ][ p ^ 1 ] = 1;
for( int dd : S[ p ] ){
int vv = ( v - dd + N ) % N;
if( ++cnt[ ( p ^ 1 ^ 1 ) * N + vv ] == S[ p ^ 1 ^ 1 ].size() ){
dp[ vv ][ p ^ 1 ^ 1 ] = 0; // どうあがいても相手が勝つ状態だけね
nlq.emplace( vv, p ^ 1 ^ 1 );
}
}
}
}
swap( lque, nlq );
}
}
{ // print result
for( int p = 0; p < 2; ++p ){
for( int i = 1; i < N; ++i ){
if( dp[ i ][ p ] == -1 ){
cout << "Loop";
} else if( dp[ i ][ p ] == 0 ){
cout << "Lose";
} else{
cout << "Win";
}
cout << " \n"[ i + 1 == N ];
}
}
}
return 0;
}
```