10pts 求助,急,悬关
查看原帖
10pts 求助,急,悬关
685602
Chtholly_Tree楼主2023/8/3 22:10
#include <bits/stdc++.h>
#define int long long

using namespace std;

map < string, int > mp;
int m, n, p, a[100], vis[100], ans = LLONG_MAX, frnum = -1;
string says[100][100];

int week (string wk) {
	if (wk == "Today is Monday.")         return 1;
	else if (wk == "Today is Tuesday.")   return 2;
	else if (wk == "Today is Wednesday.") return 3;
	else if (wk == "Today is Thursday.")  return 4;
	else if (wk == "Today is Friday.")    return 5;
	else if (wk == "Today is Saturday.")  return 6;
	else if (wk == "Today is Sunday.")    return 7;
	else return -1;
}

void dfs (int cur) { // 1 代表真话,0 代表假话
	if (cur > m) {
		int cnt = 0;
		for (int i = 1; i <= m; i++) {
			cnt += !vis[i];
		}
		if (cnt != n) return;
		int isfr[40];
		int wek = 0;
		memset (isfr, -1, sizeof isfr); // 犯人 1,普通人 0
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= a[i]; j++) {
				string tsay = says[i][j];
				if (tsay == "I am guilty.") {
					if (vis[i] == 1) {
						if (isfr[i] == -1 || isfr[i] == 1) isfr[i] = 1;
						else return;
					}
					else {
						if (isfr[i] == -1 || isfr[i] == 0) isfr[i] = 0;
						else return;
					}
				}
				else if (tsay == "I am not guilty.") {
					if (vis[i] == 1) {
						if (isfr[i] == -1 || isfr[i] == 0) isfr[i] = 0;
						else return;
					}
					else {
						if (isfr[i] == -1 || isfr[i] == 1) isfr[i] = 1;
						else return;
					}
				}
				else if (tsay.find("is guilty.") != -1) {
					string f;
					for (int i = 0; i < tsay.size(); i++) {
						if (tsay[i] != ' ') f += tsay[i];
					}
					int peonumber = mp[f];
					if (vis[i] == 1) {
						if (isfr[peonumber] == -1 || isfr[peonumber] == 1) isfr[peonumber] = 1;
						else return;
					}
					else {
						if (isfr[peonumber] == -1 || isfr[peonumber] == 0) isfr[peonumber] = 0;
						else return;
					}
				}
				else if (tsay.find("is not guilty.") != -1) {
					string f;
					for (int i = 0; i < tsay.size(); i++) {
						if (tsay[i] != ' ') f += tsay[i];
					}
					int peonumber = mp[f];
					if (vis[i] == 1) {
						if (isfr[peonumber] == -1 || isfr[peonumber] == 1) isfr[peonumber] = 1;
						else return;
					}
					else {
						if (isfr[peonumber] == -1 || isfr[peonumber] == 0) isfr[peonumber] = 0;
						else return;
					}
				}
				else if (tsay.find("Today is") != -1) {
					int thisweek = week(tsay);
					if (vis[i] == 1) {
						if (wek == 0 || wek == thisweek) wek = thisweek;
						else return;
					}
					else {
						if (wek == thisweek) return;
					}
				}
			}
		}
		int realfr = -1;
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (isfr[i] == 1) cnt++, realfr = i;
		}
		if (cnt > ans) return;
		else ans = cnt;
		if (cnt == 1) frnum = realfr;
		return;
	}
	vis[cur] = 0;
	dfs(cur + 1);
	vis[cur] = 1;
	dfs(cur + 1);
}

signed main () {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n >> p;
	for (int i = 1; i <= m; i++) {
		string s; cin >> s;
		mp[s] = i;
	}
	for (int i = 1; i <= p; i++) {
		string name, say;
		cin >> name;
		cin.get();
		getline(cin, say);
		name = name.substr(0, name.size() - 1);
		int peo = mp[name];
		a[peo]++;
		says[peo][a[peo]] = say;
	}
	dfs(1);
	if (ans >= 2) {
		cout << "Cannot Determine\n";
	}
	else if (ans == LLONG_MAX || frnum == -1) {
		cout << "Impossible\n";
	}
	else {
		for (map < string, int > ::iterator it = mp.begin(); it != mp.end(); it++) {
			if (it -> second == frnum) {
				cout << it -> first << endl;
				return 0;
			}
		}
	}
	return 0;
}
2023/8/3 22:10
加载中...