제출 #1143370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143370		snpmrnhlol	새로운 문제 (POI13_ins)	C++20	0 / 100	3305 ms	196608 KiB

ins

#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) || n >= 30){
        cout<<"TAK\n";
    }else{
        cout<<"NIE\n";
    }
    return 0;
}

• Subtask 1: 0 / 100