제출 #1168253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168253		Jawad_Akbar_JJ	새로운 문제 (POI13_spa)	C++20	12 / 100	788 ms	66652 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)], Seen2[(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;
	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 DFS(int n, int x){
	if (x == Y){
		cout<<"TAK\n";
		exit(0);
	}
	if (Seen[x] or Seen2[x])
		return;
	Seen[x] = 1;
	for (int i=0;i<n;i++)
		dfs(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, K;i<=k;i++)
		K = get(n), seen2[K] = Seen2[K] = 1;
	
	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);

	DFS(n, X);

	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