#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)
const int maxn = 19;
map<pair<pair<int , int> , int> , bool> mp;
int n , who[maxn];
bool is[maxn];
vector<int> adj[maxn];
int get_dp(int mask1 , int mask2 , int v)
{
pair<pair<int , int> , int> tmp = {{mask1 , mask2} , v};
if(mp.count(tmp))
return mp[tmp];
for(auto u : adj[v])
{
int w;
if(bit(mask1 , u))
w = 1;
else if(bit(mask2 , u))
w = 0;
else
{
if(is[u])
w = get_dp(mask1 | mask2 | (1 << u) , 0 , u);
else
w = get_dp(mask1 , mask2 | (1 << u) , u);
}
if(w == who[v])
{
mp[tmp] = who[v];
return who[v];
}
}
mp[tmp] = 1 - who[v];
return 1 - who[v];
}
int DFS(int v)
{
sort(adj[v].begin() , adj[v].end());
if((int)adj[v].size() > 1 && DFS(adj[v][1]) == who[v])
return who[v];
if(adj[v][0] == v && is[v] == who[v])
return who[v];
return !who[v];
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
n = a.size();
bool all = 1;
for(int i = 0; i < n; i++)
{
all &= who[i];
is[i] = r[i] , who[i] = a[i];
}
bool f = 1;
for(int i = 0; i < (int)u.size(); i++)
{
f &= (v[i] - u[i] <= 1) && (v[i] >= u[i]);
adj[u[i]].pb(v[i]);
}
vector<int> ans;
if(n <= 15)
{
for(int i = 0; i < n; i++)
{
if(is[i])
ans.pb(get_dp(1 << i , 0 , i));
else
ans.pb(get_dp(0 , (1 << i) , i));
}
}
else if(f)
{
for(int i = 0; i < n; i++)
ans.pb(DFS(i));
}
else if(all)
{
}
else
{
}
return ans;
}
