记录编号	124531	评测结果	AAAAAAAAAAAAA
题目名称	[NOIP 2003]侦探推理	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-10-04 15:52:08	内存使用	0.32 MiB

#include <cstdio>
#include <cstring>

struct plot {int k,n;}p[30][110],tmp; // k==1 -> is guilty; k==2 -> isn't guilty; k==3 -> today is XXX

int M,N,P,i,s[30],sub,ans;
char nm[30][260],str[260],name[260],name2[260];
bool f[30];

int check()
{
	int i,j,g[30],d[10],cnt=0,cri;
	plot tmp;
	memset(g,-1,sizeof(g));
	memset(d,-1,sizeof(d));
	for (i=1;i<=M;++i)
		for (j=1;j<=s[i];++j)
		{
			tmp=p[i][j];
			if (!f[i]&&tmp.k==1) tmp.k=2;
			else if (!f[i]&&tmp.k==2) tmp.k=1;
			else if (!f[i]&&tmp.k==3) tmp.k=4;
			else if (!f[i]&&tmp.k==4) tmp.k=3;
			switch (tmp.k)
			{
				case 1:
					if (g[tmp.n]==-1) g[tmp.n]=1;
					else if (g[tmp.n]==0) return 0;
					break;
				case 2:
					if (g[tmp.n]==-1) g[tmp.n]=0;
					else if (g[tmp.n]==1) return 0;
					break;
				case 3:
					if (d[tmp.n]==-1) d[tmp.n]=1;
					else if (d[tmp.n]==0) return 0;
					break;
				case 4:
					if (d[tmp.n]==-1) d[tmp.n]=0;
					else if (d[tmp.n]==1) return 0;
			}
		}
	for (i=1;i<=7;++i) if (d[i]==1) ++cnt;
	if (cnt>1) return 0; cnt=0;
	for (i=1;i<=M;++i)
		if (g[i]==1) {++cnt; cri=i;}
	if (cnt==1) return cri;
	if (cnt>1) return 0; cnt=0;
	for (i=1;i<=M;++i)
		if (g[i]==-1) {++cnt; cri=i;}
	if (cnt==1) return cri;
	if (cnt>1) return -1;
	return 0;
}

void dfs(int dep,int tot)
{
	if (dep>M)
	{
		if (tot<=N) return;
		//for (int i=1;i<=M;++i) putchar(48+f[i]); putchar('\n');
		int tmp=check();
		//printf("%d\n",tmp);
		if (tmp&&!ans) ans=tmp;
		else if (tmp>0&&ans>0&&ans!=tmp) ans=-1;
		return;
	}
	f[dep]=1; dfs(dep+1,tot);
	if (tot<=N) {f[dep]=0; dfs(dep+1,tot+1);}
}

int main()
{
	freopen("logic.in","r",stdin);
	freopen("logic.out","w",stdout);
	scanf("%d%d%d",&M,&N,&P);
	for (i=1;i<=M;++i) scanf("%s",nm[i]);
	while (P--)
	{
		tmp=(plot){0,0};
		scanf("%s%s",name,name2); name[strlen(name)-1]='\0';
		for (i=1;i<=M;++i) if (strcmp(name,nm[i])==0) sub=i;
		fgets(str,sizeof(str),stdin);
		if (str[strlen(str)-1]=='\n') str[strlen(str)-1]='\0';
		if (strcmp(str," am guilty.")==0)
			{if (strcmp(name2,"I")==0) tmp=(plot){1,sub};}
		else if (strcmp(str," am not guilty.")==0)
			{if (strcmp(name2,"I")==0) tmp=(plot){2,sub};}
		else if (strcmp(str," is guilty.")==0)
			{for (i=1;i<=M;++i) if (strcmp(name2,nm[i])==0) tmp=(plot){1,i};}
		else if (strcmp(str," is not guilty.")==0)
			{for (i=1;i<=M;++i) if (strcmp(name2,nm[i])==0) tmp=(plot){2,i};}
		else if (strcmp(str," is Monday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,1};}
		else if (strcmp(str," is Tuesday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,2};}
		else if (strcmp(str," is Wednesday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,3};}
		else if (strcmp(str," is Thursday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,4};}
		else if (strcmp(str," is Friday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,5};}
		else if (strcmp(str," is Saturday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,6};}
		else if (strcmp(str," is Sunday.")==0)
			{if (strcmp(name2,"Today")==0) tmp=(plot){3,7};}
		p[sub][++s[sub]]=tmp;
		//printf("sub=%d type=%d num=%d\n",sub,tmp.k,tmp.n);
	}
	dfs(1,1);
	if (ans==-1) printf("Cannot Determine\n");
	else if (ans==0) printf("Impossible\n");
	else printf("%s\n",nm[ans]);
	fclose(stdin); fclose(stdout);
	return 0;
}