P1039 [NOIP2003 提高组] 侦探推理

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id;
	int infor;
	node(int a,int b)
	{
		id=a;infor=b;
	}
};

int n,m,p;
string s;
vector<node> say[25];
string reflect[25];

bool choose[25];

int week[10];
int person[25];
int cnt;
int ans,guilty;


void check()
{
	memset(week,0,sizeof(week));
	memset(person,0,sizeof(person));
	cnt=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<say[i].size();j++)
		{
			if(choose[i])
			{
				if(say[i][j].id==1)
				{
					if(person[say[i][j].infor]==1)return;
					person[say[i][j].infor]=2;
				}
				else if(say[i][j].id==2)
				{
					if(person[say[i][j].infor]==2)return;
					person[say[i][j].infor]=1;
				}
				else
				{
					if(week[say[i][j].infor]==1)return;
					week[say[i][j].infor]=2;
				}
			}
			else
			{
				if(say[i][j].id==1)
				{
					if(person[say[i][j].infor]==2)return;
					person[say[i][j].infor]=1;
				}
				else if(say[i][j].id==2)
				{
					if(person[say[i][j].infor]==1)return;
					person[say[i][j].infor]=2;
				}
				else
				{
					if(week[say[i][j].infor]==2)return;
					week[say[i][j].infor]=1;
				}
			}
		}
	}
	
	int week1=0,week2=0;
	for(int i=1;i<=7;i++)
	{
		if(week[i]==1)week1++;
		else if(week[i]==2)week2++;
	}
	if(week1>1 || week2==7)
		return;
	
	int cnt1=0,cnt2=0;
	for(int i=1;i<=m;i++)
	{
		if(person[i]==1)cnt1++;
		else if(person[i]==2)cnt2++;
	}
	if(cnt1>1 || cnt2==m)
		return;
		
	ans++;
//	cout<<"6ao\n";
//	for(int i=1;i<=m;i++)
//	{
//		cout<<choose[i]<<" ";
//	}cout<<"\n";
	if(cnt1==1)
		for(int i=1;i<=m;i++)
		{
			if(person[i]==1)
			{
				
				if((guilty!=0 && guilty!=i)|| guilty==-1)
				{
					guilty=-1;
					return;
				}
				
				guilty=i;
				break;
			}
		}
	else if(cnt2==m-1)
	{
		for(int i=1;i<=m;i++)
		{
			if(person[i]==0)
			{
				if((guilty!=0 && guilty!=i)|| guilty==-1)
				{
					guilty=-1;
					return;
				}
				
				guilty=i;
				break;
			}
		}
	}
	else if(cnt2<m-1)
	{
		guilty=-1;
	}
}



void dfs(int x,int t)
{
	if(t==n)
	{
//		for(int i=1;i<=m;i++)
//		{
//			cout<<choose[i]<<" ";
//		}
//		cout<<"\n";
		check();
		return;
	}
	if(x==m+1)
	{
		return;
	}
	dfs(x+1,t);
	choose[x]=1;
	dfs(x+1,t+1);
	choose[x]=0;
}

int main()
{
	cin>>m>>n>>p;
	for(int i=1;i<=m;i++)
	{
		cin>>reflect[i];
	}
	string s;
	for(int i=1;i<=p;i++)
	{
		s.clear();
		while(s[s.length()-1]!=':')
		{
			cin>>s;
		}
		
		s.erase(s.end()-1);
		int k=0;
		for(int j=1;j<=m;j++)
		{
			if(s==reflect[j])
			{
				k=j;
				break;
			}
		}
		s.clear();
		cin>>s;
		if(s=="I")
		{
			cin>>s;
			if(s!="am")continue;
			cin>>s;
			if(s=="not")
			{
				cin>>s;
				if(s=="guilty.")
					say[k].push_back(node(2,k));
			}
			else if(s=="guilty.")
			{
				say[k].push_back(node(1,k));
			}
		}
		else if(s=="Today")
		{
			cin>>s;
			if(s=="is")
			cin>>s;
			s.erase(s.end()-1);
			if(s=="Monday")
			{
				say[k].push_back(node(3,1));
			}
			else if(s=="Tuesday")
			{
				say[k].push_back(node(3,2));
			}
			else if(s=="Wednesday")
			{
				say[k].push_back(node(3,3));
			}
			else if(s=="Thursday")
			{
				say[k].push_back(node(3,4));
			}
			else if(s=="Friday")
			{
				say[k].push_back(node(3,5));
			}
			else if(s=="Saturday")
			{
				say[k].push_back(node(3,6));
			}
			else if(s=="Sunday")
			{
				say[k].push_back(node(3,7));
			}
		}
		else
		{
			int kk=0;
			for(int j=1;j<=m;j++)
			{
				if(s==reflect[j])
				{
					kk=j;
					break;
				}
			}
			if(kk==0)continue;
			cin>>s;
			if(s!="is")continue;
			cin>>s;
			if(s=="not")
			{
				cin>>s;
				if(s=="guilty.")
					say[k].push_back(node(2,kk));
			}
			else if(s=="guilty.")
			{
				say[k].push_back(node(1,kk));
			}
		}
	}
//	for(int i=1;i<=m;i++)
//	{
//		cout<<i<<" \n";
//		for(int j=0;j<say[i].size();j++)
//		{
//			cout<<say[i][j].id<<" "<<say[i][j].infor<<"\n";
//		}
//	}
	dfs(1,0);
	if(guilty==0)
	{
		cout<<"Impossible";
	}
	else if(guilty==-1)
	{
		cout<<"Cannot Determine";
	}
	else
	{
		cout<<reflect[guilty];
	}
}