| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1168236 | Faisal_Saqib | Walk (POI13_spa) | C++17 | 0 ms | 0 KiB |
#include <bitset>
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
#define ll long long
int n,k;
char c;
ll asp=0;
// 10000000040
// 2e9 = 2000000000
bitset<10000000000> ban[2];
ll read()
{
asp=0;
for(int i=0;i<n;i++)
{
cin>>c;
asp<<=1;
asp+=c-'0';
}
return asp;
}
ll pw2[70];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
if(n<=44)
{
}
else
{
exit(-1);
}
pw2[0]=1;
for(int i=1;i<=n;i++)
pw2[i]=2ll*pw2[i-1];
ll st=read(),ed=read();
for(int i=0;i<k;i++)
{
ll c=read();
ban[0][c]=ban[1][c]=1;
}
// lets do a double sided bfs
// better time complexity
queue<ll>pq;
ban[0][st]=1;
pq.push(st);
ban[1][ed]=1;
pq.push(ed);
ll op=0;
while(pq.size())
{
ll x=pq.front();
pq.pop();
// op++;
// ll x=xa.first;
if(ban[0][x]&ban[1][x])
{
cout<<"TAK"<<endl;
return 0;
}
// if(op*n >= 2e9)
// {
// break;
// }
for(int bi=0;bi<n;bi++)
{
ll y=x^pw2[bi];
for(int at=0;at<2;at++)
{
if(ban[at][x] and !ban[at][y])
{
if(ban[1-at][y])
{
cout<<"TAK"<<endl;
return 0;
}
ban[at][y]=1;
pq.push(y);
}
}
}
}
cout<<"NIE"<<endl;
return 0;
}