Submission #1168271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168271		Jawad_Akbar_JJ	Walk (POI13_spa)	C++20	12 / 100	1831 ms	148972 KiB

spa

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

using namespace std;
#define int long long
int  X, Y, o = 1;
int Seen[(1<<22)];
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;

	clock_t start, end;
	start = clock();

	while (!Q.empty()){
		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);
			cur ^= (o<<vec[i]);
		}
		end = clock();	
		double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
		if (time_taken >= 0.900)
			return;
	}
}

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);
	}

	clock_t start, end;
	
	start = clock();
	while (!Q.empty()){
		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);
			cur ^= (o<<vec[i]);
		}
		end = clock();
	
		double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
		if (time_taken >= 0.90000)
			return;
	}
}


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

signed main(){
	srand(time(0));
	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, K;i<=k;i++)
		K = get(n), seen2[K] = Seen[K] = 1;
	
	dfs11(n, X);
	// return 0;

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

	for (int i=1;i<rand() % 10;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