Submission #1168377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168377		ghammazhassan	Walk (POI13_spa)	C++20	12 / 100	2879 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);
}
string its(int x){
	string s;
	while (x>1){
		s+='0'+x%2;
		x/=2;
	}
	while (s.size()<n){
		s+='0';
	}
	reverse(s.begin(),s.end());
	return s;
}
int sti(string s){
	int x=0;
	for (int i=0;i<n;i++){
		x+=(1<<(n-i-1))*(int)(s[i]-'0');
	}
	return x;
}
void solve()
{	
	cin >> n >> k;
	string s,t;
	cin >> s >> t;
	x=sti(s);
	y=sti(t);
	map<string,int>d;
	for (int e=0;e<k;e++){
		c=0;
		string f;
		cin >> f;
		d[f]=1;
	}
	map<string,int>vi;
	queue<string>o;
	o.push(s);
	vi[s]=1;
	while (!o.empty()){
		string h=o.front();
		o.pop();
		for (int i=0;i<n;i++){
			h[i]='0'+((h[i]-'0')^1);
			if (vi[h] or d[h]){
				vi[h]=1;
				h[i]='0'+((h[i]-'0')^1);
				continue;
			}
			vi[h]=1;
			o.push(h);
			h[i]='0'+((h[i]-'0')^1);
		}
	}
	if (vi[t]){
		cout << "TAK" << endl;
	}
	else{
		cout << "NIE" << endl;
	}
	// while(s!=t){
	// 	bool f=0;
	// 	for (int i=0;i<n;i++){
	// 		if (s[i]!=t[i]){
	// 			s[i]='0'+((s[i]-'0')^1);
	// 			if (d[sti(s)]){
	// 				s[i]='0'+((s[i]-'0')^1);
	// 				continue;
	// 			}
	// 			f=1;
	// 		}
	// 	}
	// 	for (int i=0;i<n;i++){
	// 		if (s[i]!=t[i]){
	// 			t[i]='0'+((t[i]-'0')^1);
	// 			if (d[sti(t)]){
	// 				t[i]='0'+((t[i]-'0')^1);
	// 				continue;
	// 			}
	// 			f=1;
	// 		}
	// 	}
	// 	if (f==0){
	// 		for (int i=n-1;i>=0;i--){
	// 			if (s[i]==t[i]){
	// 				t[i]='0'+((t[i]-'0')^1);
	// 				if (d[sti(t)]){
	// 					t[i]='0'+((t[i]-'0')^1);
	// 					continue;
	// 				}
	// 				f=1;
	// 			}
	// 		}
	// 	}
	// }
	// cout << s << endl;
	// cout << t << endl;
	// if (s==t){
	// 	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: 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