Submission #1168401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168401		Jawad_Akbar_JJ	Walk (POI13_spa)	C++20	12 / 100	612 ms	201684 KiB

spa

#include <iostream>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;
#define int long long
int  X, Y, o = 1, Sn[1<<23];
map<int, int> seen, seen1, seen2;
vector<int> vec;
int get(int n, int inp = 0){
	while (n--){
		char c;
		cin>>c;
		inp = inp * 2 + c - '0';
	}
	return inp;
}

void dfs(int n, int x, int num = 0){
	queue<int> Q;
	Q.push(x);
	seen[x] = 1;
	while (!Q.empty() and num < 100000){
		int cur = Q.front();
		Q.pop();
		for (int i=0;i<n;i++){
			cur ^= (o<<vec[i]);
			if (!seen2[cur] and !seen[cur])
				seen[cur] = 1, Q.push(cur), num++;
			cur ^= (o<<vec[i]);
		}
	}
}

void dfs2(int n, int x, int num = 0){
	queue<int> Q;
	Q.push(x);
	seen1[x] = 1;
	if (seen[x] == 1){
		cout<<"TAK\n";
		exit(0);
	}
	while (!Q.empty() and num < 100000){
		int cur = Q.front();
		Q.pop();
		for (int i=0;i<n;i++){
			cur ^= (o<<vec[i]);
			if (seen[cur]){
				cout<<"TAK\n";
				exit(0);
			}
			if (!seen2[cur] and !seen1[cur])
				seen1[cur] = 1, Q.push(cur), num++;
			cur ^= (o<<vec[i]);
		}
	}
}

void dfs111(int n, int x){
	if (x == Y){
		cout<<"TAK\n";
		exit(0);
	}
	if (Sn[x])
		return;
	Sn[x] = 1;
	for (int i=0;i<n;i++)
		dfs111(n, x ^ (1<<i));
}


signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k;
	cin>>n>>k;

	X = get(n), Y = get(n);
	for (int i=1;i<=k;i++){
		int K = get(n);
		seen2[K] = 1, Sn[K] = 1;
	}
	
	dfs111(n, X);

	for (int i=0;i<n;i++)
		vec.push_back(i);
	
	for (int i=1;i<100;i++)
		random_shuffle(begin(vec), end(vec));
	dfs(n, X);

	for (int i=1;i<100;i++)
		random_shuffle(begin(vec), end(vec));
	dfs2(n, Y);

	cout<<"NIE\n";
}

• 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