Submission #1168343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168343		ghammazhassan	Walk (POI13_spa)	C++20	0 / 100	1163 ms	327680 KiB

spa

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define fi first
#define se second
const int N=5e6+5;
const int M=1e9+7;
const int LOG = 20;
int n , m , k , c , d , t=1 , q=1 , x , y , p[N] , l , r;
vector<vector<int>>a(N);

int bp(int x,int y){
	x=x%M;
	if (y==0)return 1;
	if (y==1)return x;
	int r=bp(x*x,y/2);
	if (y%2)r*=x;
	r%=M;
	return r;
}
int inv(int x){
	return bp(x,M-2);
}

void solve()
{	
	cin >> n >> k;
	string s,t;
	cin >> s >> t;
	x=0,y=0;
	for (int i=0;i<n;i++){
		x+=(1<<(n-i-1))*(int)(s[i]-'0');
	}
	for (int i=0;i<n;i++){
		y+=(1<<(n-i-1))*(int)(t[i]-'0');
	}
	vector<int>o(1<<n);
	for (int e=0;e<k;e++){
		c=0;
		string f;
		cin >> f;
		for (int i=0;i<n;i++){
			c+=(1<<(n-i-1))*(f[i]-'0');
		}
		o[c]=1;
	}
	for (int i=0;i<(1<<n);i++){
		if (o[i])continue;
		string u;
		for (int j=n-1;j>=0;j--){
			u+=('0'+(((1<<j)|i)==i));
		}
		for (int j=0;j<n;j++){
			u[j]='0'+((u[j]-'0')^1);
			c=0;
			for (int r=0;r<n;r++){
				c+=(1<<(n-r-1))*(u[r]-'0');
			}
			u[j]='0'+((u[j]-'0')^1);
			if (o[c])continue;
			a[c].push_back(i);

		}
	}
	queue<int>oi;
	vector<int>vi(1<<n),di(1<<n);
	oi.push(x);
	vi[x]=1;
	while (!oi.empty()){
		int h=oi.front();
		oi.pop();
		for (int i:a[h]){
			if (vi[i])continue;
			vi[i]=1;
			di[i]=di[h]+1;
			oi.push(i);
		}
	}
	if (di[y]){
		cout << "TAK" << endl;
	}
	else{
		cout << "NIE" << endl;
	}
}
signed main()	
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed<<setprecision(9);
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
    	solve();
    	q++;
    }
}

• Subtask 1: 0 / 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