第8个点 RE 求助
查看原帖
第8个点 RE 求助
108610
Dzhao楼主2021/2/16 21:27
#include<bits/stdc++.h>
using namespace std;
const int N=305,M=305,P=305;
char na[N][M],s[M],tmp[M];int cnt=0,n,m,k,g[N],d[10],flg;bool op[N],flag,sha[N];
struct node {int id,type,x;}a[P];
inline int Day(char *s)
{
	if(strcmp(s,"Monday.")==0) return 1;
	if(strcmp(s,"Tuesday.")==0) return 2;
	if(strcmp(s,"Wednesday.")==0) return 3;
	if(strcmp(s,"Thursday.")==0) return 4;
	if(strcmp(s,"Friday.")==0) return 5;
	if(strcmp(s,"Saturday.")==0) return 6;
	if(strcmp(s,"Sunday.")==0) return 7;
	return -1;
}
void dfs(int u,int step)
{
	if(u>n)
	{
		if(step!=0) return;
		memset(g,-1,sizeof(g));
		memset(d,-1,sizeof(d));
		bool ok=0;
		for(int i=1;i<=cnt;i++)	
			if(op[a[i].id]) 
			{
				if(a[i].type==1) 
				{
					if(g[a[i].id]==0) return;
					g[a[i].id]=1;
				}
				if(a[i].type==2) 
				{
					if(g[a[i].id]==1) return;
					g[a[i].id]=0;
				}
				if(a[i].type==3)
				{
					if(g[a[i].x]==0) return;
					g[a[i].x]=1; 
				}
				if(a[i].type==4)
				{
					if(g[a[i].x]==1) return;
					g[a[i].x]=0; 
				}
				if(a[i].type==5) 
				{
					if(d[a[i].x]==0) return;
					d[a[i].x]=1;
				}
			} 
			else 
			{
				if(a[i].type==1) 
				{
					if(g[a[i].id]==1) return;
					g[a[i].id]=0;
				}
				if(a[i].type==2) 
				{
					if(g[a[i].id]==0) return;
					g[a[i].id]=1;
				}
				if(a[i].type==3)
				{
					if(g[a[i].x]==1) return;
					g[a[i].x]=0; 
				}
				if(a[i].type==4)
				{
					if(g[a[i].x]==0) return;
					g[a[i].x]=1; 
				}
				if(a[i].type==5) 
				{
					if(d[a[i].x]==1) return;
					d[a[i].x]=0;
				}
			}
		int sum=0;
		for(int i=1;i<=7;i++) if(d[i]==1) sum++;
		if(sum>1) return;
		sum=0;int zui;
		for(int i=1;i<=n;i++) if(g[i]==0) sum++;
		if(sum==n-1) for(int i=1;i<=n;i++) if(g[i]!=0) zui=i;
		sum=0;
		for(int i=1;i<=n;i++) if(g[i]==1) sum++,zui=i; 
		if(sum>1) return;
		sha[zui]=1;
		return;
	}
	op[u]=1;
	if(step) dfs(u+1,step-1);
	op[u]=0;
	dfs(u+1,step);
}

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>na[i];
	gets(s);
	for(int i=1;i<=k;i++)
	{
		gets(s);int len=strlen(s),id=-1,x=-1,pos;
        s[len-1]=0,len--;
		for(int j=0;j<len;j++) 
			if(s[j]==':')
			{
				memset(tmp,0,sizeof(tmp));
				pos=j+2;
				for(int t=0;t<j;t++) tmp[t]=s[t];
				for(int t=1;t<=n;t++)
					if(strcmp(tmp,na[t])==0) id=t;
				break;
			}
		if(id==-1) continue;
		memset(tmp,0,sizeof(tmp));
		for(int j=pos;j<len;j++) tmp[j-pos]=s[j];
		if(strcmp(tmp,"I am guilty.")==0) {a[++cnt]=(node){id,1,0};continue;}
		if(strcmp(tmp,"I am not guilty.")==0) {a[++cnt]=(node){id,2,0};continue;}
		for(int j=pos;j<len;j++) s[j-pos]=s[j];
		for(int j=len-pos;j<len;j++) s[j]=0;len-=pos;
		for(int j=0;j<len;j++) 
			if(s[j]==' ')
			{
				pos=j+1;
				memset(tmp,0,sizeof(tmp));
				for(int t=0;t<j;t++) tmp[t]=s[t];
				for(int t=1;t<=n;t++)
					if(strcmp(tmp,na[t])==0) x=t;
				if(strcmp(tmp,"Today")==0) x=0; 
				break;
			}
		if(x==-1) continue;  	
		if(x==0) 
		{
			if(!(s[6]=='i' && s[7]=='s' && s[8]==' ')) continue;
			memset(tmp,0,sizeof(tmp));
			for(int t=9;t<len;t++) tmp[t-9]=s[t];
			x=Day(tmp);
			if(x==-1) continue;
			a[++cnt]=(node){id,5,x};
		}
		else 
		{
			for(int t=pos;t<len;t++) tmp[t-pos]=s[t];
			if(strcmp(tmp,"is guilty.")==0) a[++cnt]=(node){id,3,x};
			else if(strcmp(tmp,"is not guilty.")==0) a[++cnt]=(node){id,4,x};
			else continue;
		}
	}
	dfs(1,n-m);
	int sum=0,sid;
	for(int i=1;i<=n;i++) if(sha[i]) sum++,sid=i;
	if(sum==0) printf("Impossible\n");
	else if(sum==1) printf("%s\n",na[sid]);
	else printf("Cannot Determine\n");  
	return 0;
}
2021/2/16 21:27
加载中...