#11WA求条
查看原帖
#11WA求条
879339
Dio_The_World楼主2025/1/21 09:02
#include <bits/stdc++.h>
#define For(i,s,e) for(int i=s;i<=e;i++)
using namespace std;
int m,n,p,pt[21],ptn[21][21],sf[21],wk[21],nxs[21],ndy[21],fxs=0,ptnl[21],sh[21],fff;
string nml[21],week[8]={"","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
bool pd(int x,int xs,int day){
//	cout<<xs<<" "<<pt[x]<<" "<<x<<endl;
	if(xs&&pt[x]==xs || xs==x&&sf[x]==1 || day&&wk[x]==day || nxs[x]&&sf[x]==2 || ptnl[x]>1)return 0;
	return 1;
}
bool pd2(int x,int xs){
	For(i,1,ptnl[x])if(ptn[x][i]==xs)return 1;
	return 0;
}
int dfs(int x,int t,int xs,int day){
	if(fxs && fxs==xs)return 0;
	if(x==m+1){
		if(t)return 0;
		int f,ms;
		if(!xs){
			f=0;
			For(i,1,m)if(!nxs[i])ms=i,f++;
			if(f==1)xs=ms;
		}
		if(!xs)return 0;
//		For(i,1,m)cout<<sh[i];cout<<endl;
        if(fxs && fxs!=xs)fff=1;
		fxs=xs;
		return 1;
	}
	int xst=0;
	if(t){
		int ynxs=nxs[x],yxs=xs,yday=day,yndy=ndy[x],ynxspt=nxs[pt[x]];
		if(pd(x,xs,day)){
//		cout<<x<<" "<<t<<" "<<xs<<" "<<day<<" "<<"\n";
			if(sf[x]==1)nxs[x]=1;
			if(sf[x]==2)xs=x;
			if(pt[x])nxs[pt[x]]=1;
			if(ptn[x][1])xs=ptn[x][1];
			if(wk[x])ndy[wk[x]]=1;
			int f,ms;
			if(!xs){
				f=0;
				For(i,1,m)if(!nxs[i])ms=i,f++;
				if(f==1)xs=ms;
			}
			if(!day){
				f=0;
				For(i,1,m)if(!ndy[i])ms=i,f++;
				if(f==1)day=ms;
			}
			sh[x]=1;
			xst=dfs(x+1,t-1,xs,day);
			sh[x]=0;
			nxs[x]=ynxs,xs=yxs,day=yday,ndy[x]=yndy,nxs[pt[x]]=ynxspt;
			if(xst==2)return 2;
		}
		
	}
	int ynxs=nxs[x],yxs=xs,yday=day,ynxsptn[21];
	For(i,1,ptnl[x])ynxsptn[i]=nxs[ptn[x][i]];
	if(xs&&pd2(x,xs) || xs==x&&sf[x]==2)return xst;
//	cout<<x<<" "<<t<<" "<<xs<<" "<<day<<" "<<(wk[x]&&ndy[wk[x]])<<"\n";
	if(day&&wk[x]&&wk[x]!=day || wk[x]&&ndy[wk[x]])return xst;	
	if(nxs[x]&&sf[x]==1 || pt[x]&&nxs[pt[x]])return xst;
	if(pt[x])xs=pt[x];
	if(wk[x])day=wk[x];
	For(i,1,ptnl[x])nxs[ptn[x][i]]=1;
	if(sf[x]==1)xs=x;
	if(sf[x]==2)nxs[x]=1;
	int f,ms;
		if(!xs){
			f=0;
			For(i,1,m)if(!nxs[i])ms=i,f++;
			if(f==1)xs=ms;
		}
		if(!day){
			f=0;
			For(i,1,m)if(!ndy[i])ms=i,f++;
			if(f==1)day=ms;
		}
	f=dfs(x+1,t,xs,day);
//	cout<<x<<" "<<t<<" "<<xs<<" "<<day<<" "<<f<<"\n";
	nxs[x]=ynxs,xs=yxs,day=yday;
	For(i,1,ptnl[x])nxs[ptn[x][i]]=ynxsptn[i];
	if(f==2)return 2;
	if(f && xst)return 1;
	return f+xst;
}
int main(){
	cin>>m>>n>>p;
	For(i,1,m){
		string nm;
		cin>>nm;
		nml[i]=nm;
	}
	int x;
	string word,cen="";
	while(cin>>word){
//		cin>>word;
		if(word[word.size()-1]==':'){
			if(cen!=""){
				if(cen.find("+I+am+guilty.")!=-1)sf[x]=1;
				if(cen.find("+I+am+not+guilty.")!=-1)sf[x]=2;
				For(i,1,m){
					if(cen.find("+"+nml[i]+"+is+guilty.")!=-1){
						pt[x]=i;
					}
					if(cen.find("+"+nml[i]+"+is+not+guilty.")!=-1){
						ptn[x][++ptnl[x]]=i;
					}
				}
				For(i,1,7){
					if(cen.find("+Today+is+"+week[i]+".")!=-1){
						wk[x]=i;
					}
				}
			}
			
			For(i,1,m)if(nml[i]+":"==word){x=i;break;}
			p--,cen="";
		}
		else cen=cen+"+"+word; 
	}
	if(cen!=""){
		if(cen.find("+I+am+guilty.")!=-1)sf[x]=1;
		if(cen.find("+I+am+not+guilty.")!=-1)sf[x]=2;
		For(i,1,m){
			if(cen.find("+"+nml[i]+"+is+guilty.")!=-1){
				pt[x]=i;
			}
			if(cen.find("+"+nml[i]+"+is+not+guilty.")!=-1){
				ptn[x][++ptnl[x]]=i;
			}
		}
		For(i,1,7){
			if(cen.find("+Today+is+"+week[i]+".")!=-1){
				wk[x]=i;
			}
		}
	}
//	For(i,1,m)cout<<pt[i]<<" "<<" "<<sf[i]<<" "<<wk[i]<<"\n";
	int ans=dfs(1,n,0,0);
	if(ans==2||fff)cout<<"Cannot Determine";
	else if(ans==1 && fxs)cout<<nml[fxs];
	else cout<<"Impossible";
}
/*
3 3 3
A
B
C
A: I am guilty. Am I??
B: C is guilty.
C: B is guilty.
*/
2025/1/21 09:02
加载中...