제출 #1168281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168281		UmairAhmadMirza	새로운 문제 (POI13_spa)	C++20	0 / 100	258 ms	23820 KiB

spa

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=61;
int const mod=1e9+7;

int n,k;
int pw[N];
set<int> rem;

bool check(int sr,int tg){
	set<int> vis;
	for(int i:rem)
		vis.insert(i);
	stack<int> st;
	st.push(sr);
	vis.insert(sr);
	while(!st.empty()){
		int nd=st.top();
		st.pop();
		for(int i=0;i<n;i++)
			if(vis.find(nd^pw[i])==vis.end()){
				vis.insert(nd^pw[i]);
				st.push(nd^pw[i]);
				if(tg==nd^pw[i] || vis.size()>3e6)
					return 1;
			}
	}
	return 0;
}


signed main(){
	cin>>n>>k;
	pw[0]=1;
	for (int i = 1; i < N; ++i)
		pw[i]=(pw[i-1]*2);
	string xx,yy;
	cin>>xx>>yy;
	int x=0,y=0;
	for(int i=0;i<n;i++){
		x+=pw[i]*(xx[i]=='1');
		y+=pw[i]*(yy[i]=='1');
	}
	for (int i = 0; i < k; ++i)
	{
		string c;
		cin>>c;
		int a=0;
		for (int i = 0; i < n; ++i)
			a+=pw[i]*(c[i]=='1');
		rem.insert(a);
	}
	if(check(x,y) && check(y,x))
		cout<<"TAK"<<endl;
	else
		cout<<"NIE"<<endl;
	return 0;
}

• 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