Submission #1168289

#TimeUsernameProblemLanguageResultExecution timeMemory
1168289Faisal_SaqibWalk (POI13_spa)C++17
12 / 100
2207 ms327680 KiB
#include <bitset> #include <iostream> #include <map> #include <set> #include <unordered_set> #include <queue> using namespace std; #define ll long long int n,k; char c; ll asp=0; // 10000000040 unordered_set<ll> 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; 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].insert(c); // ban[1].insert(c); } // lets do a double sided bfs // better time complexity queue<ll>pq; ban[0].insert(st); pq.push(st); // ban[1].insert(ed); // pq.push(ed); ll op=0; while(pq.size()) { ll x=pq.front(); pq.pop(); // op++; bool p=ban[0].find(x)!=end(ban[0]); bool q=0; // bool q=ban[1].find(x)!=end(ban[1]); if(p and q) { cout<<"TAK"<<endl; return 0; } // if(op*n >= 2e9) // { // break; // } for(int bi=0;bi<n;bi++) { ll y=x^pw2[bi]; if(p and ban[0].find(y)==end(ban[0])) { // if(ban[1].find(y)!=end(ban[1])) if(y==ed) { cout<<"TAK"<<endl; return 0; } ban[0].insert(y); pq.push(y); } // if(q and ban[1].find(y)==end(ban[1])) // { // if(ban[0].find(y)!=end(ban[0])) // { // cout<<"TAK"<<endl; // return 0; // } // ban[1].insert(y); // pq.push(y); // } } } cout<<"NIE"<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...