Submission #1143372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143372		snpmrnhlol	Walk (POI13_spa)	C++20	12 / 100	5106 ms	324720 KiB

spa

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int K = 1e6;
int calc(string &x){
    int nr = 0;
    for(int i = 0;i < x.size();i++){
        nr = nr*2 + x[i] - '0';
    }
    return nr;
}
set <int> vis;
int st, en;
int n, k;
bool dfs(int x){
    if(vis.find(x) != vis.end())return 0;
    vis.insert(x);
    if(x == en)return 1;
    bool ok = 0;
    for(int i = n/2;i < n;i++){
        if((x^en)>>i&1){
            ok|=dfs(x^(1ll<<i));
            if(ok)break;
        }
    }
    if(ok)return 1;
    for(int i = n/2 - 1;i >= 0;i--){
        if((x^en)>>i&1){
            ok|=dfs(x^(1ll<<i));
            if(ok)break;
        }
    }
    if(ok)return 1;
    for(int i = 0;i < n;i++){
        if(!((x^en)>>i&1)){
            ok|=dfs(x^(1ll<<i));
            if(ok)break;
        }
    }
    return ok;
}
int32_t main(){
    cin>>n>>k;
    string a, b;
    cin>>a>>b;
    st = calc(a);
    en = calc(b);
    for(int i = 0;i < k;i++){
        cin>>a;
        vis.insert(calc(a));
    }
    if(dfs(st)){
        cout<<"TAK\n";
    }else{
        cout<<"NIE\n";
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13