Submission #1168124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168124		Rafiullah	Walk (POI13_spa)	C++20	88 / 100	5056 ms	64932 KiB

spa

#include <bits/stdc++.h>
#define fi first
#define se second
#define bupo __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define int long long
const int LOG = 16, MAXB = 1<<LOG, SQR = 1<<10;
const ll MOD = 1e9+7;
const int mod = 998244353;
const int N = 2e6 + 5;
set<int> no;
int n,k;
int t(string num){
    int e = 0;
    for(int i = num.size() - 1 ; i >= 0 ;  i --) e += (1LL << i) * (num[i] == '1');
    return e;
}
int f(int x,int y){
    vector<int> Vec = {x};set<int> S = {x};
    while(Vec.size()){
        vector<int> Q;
        for(int num : Vec){
            for(int i = 0 ; i < n ; i ++){
                int other = (num ^ (1LL << i));
                if(S.find(other) == S.end() and no.find(other) == no.end())
                    Q.push_back(other), S.insert(other);
            }
        }
        if(Q.size() == 0 and S.find(y) != S.end())return 1;
        if(Q.size() > 2 * k)return 1;
        Vec = Q;
    }
    return 0;
}
void solve(){
    cin >> n >> k;
    string a,b;cin >> a >> b;
    int A = t(a);int B = t(b);
    for(int i = 0 ; i < k ;  i ++){
        string tt;cin >> tt;
        no.insert(t(tt));
    }
    if(f(A,B) and f(B,A))cout << "TAK" << '\n';
    else cout << "NIE" << '\n';
}
signed main(){
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
}

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